怪盜基德的滑翔翼 題解

怪盜基德的滑翔翼

總時間限制: 

1000ms

 

記憶體限制: 

65536kB

描述

 

怪盜基德是一個充滿傳奇色彩的怪盜，專門以珠寶為目標的超級盜竊犯。而他最為突出的地方，就是他每次都能逃脫中村警部的重重圍堵，而這也很大程度上是多虧了他隨身攜帶的便於操作的滑翔翼。

有一天，怪盜基德像往常一樣偷走了一顆珍貴的鑽石，不料卻被柯南小朋友識破了偽裝，而他的滑翔翼的動力裝置也被柯南踢出的足球破壞了。不得已，怪盜基德只能操作受損的滑翔翼逃脫。

假設城市中一共有N幢建築排成一條線，每幢建築的高度各不相同。初始時，怪盜基德可以在任何一幢建築的頂端。他可以選擇一個方向逃跑，但是不能中途改變方向（因為中森警部會在後面追擊）。因為滑翔翼動力裝置受損，他只能往下滑行（即：只能從較高的建築滑翔到較低的建築）。他希望儘可能多地經過不同建築的頂部，這樣可以減緩下降時的衝擊力，減少受傷的可能性。請問，他最多可以經過多少幢不同建築的頂部（包含初始時的建築）？

 

輸入

輸入數據第一行是一個整數K（K < 100），代表有K組測試數據。
每組測試數據包含兩行：第一行是一個整數N(N < 100)，代表有N幢建築。第二行包含N個不同的整數，每一個對應一幢建築的高度h（0 < h < 10000），按照建築的排列順序給出。

輸出

對於每一組測試數據，輸出一行，包含一個整數，代表怪盜基德最多可以經過的建築數量。

樣例輸入

3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

樣例輸出

6
6
9

　　當我們看到題目之後，第一個反應就是最長下降子序列，事實上，這確實是最長下降子序列，但是，我們必須要註意到一句話：初始時，怪盜基德可以在任何一幢建築的頂端。他可以選擇一個方向逃跑，但是不能中途改變方向（因為中森警部會在後面追擊）。咦？這是什麼意思，未必還是雙向的啊！嗯，想到這裡，你就已經把大概的演算法給設計出來了，沒錯，就是雙向最長下降子序列...（上述名字，純屬自創，如有雷同，純屬巧合）。那麼接下來就是代碼實現的問題了。首先就是雙向存儲的問題，我們可以開一個a[2][101]來記錄高度，其中，a[1][i]代表著從左往右走第i個建築的高度，a[2][i]代表從右往左第i個建築的高度。相同的，我們設置f[2][101]來記錄從左往右（從右往左）數飛到第i個建築時最多經過的建築個數，然後在將f數組掃一遍，找出最大值，就可以了。接下來就是代碼了。

 1 program NOI4977;
 2 var
 3    f:array[1..2,0..101] of longint;
 4    a:array[1..2,0..101] of longint;
 5    i,j,k,n,m,max:longint;
 6 begin
 7      readln(m);
 8      for k:=1 to m do
 9      begin
10           fillchar(f,sizeof(f),0);
11           readln(n);
12           for i:=1 to n do
13               begin
14                    read(a[1,i]);
15                    a[2,n-i+1]:=a[1,i];
16               end;
17           f[1,n]:=1;
18           f[2,n]:=1;
19           for i:=n-1 downto 1 do
20               begin
21                    max:=0;
22                    for j:=i+1 to n do
23                        if (a[1,i]>a[1,j]) and (f[1,j]>max) then
24                           max:=f[1,j];
25                    f[1,i]:=max+1;
26               end;
27           for i:=n-1 downto 1 do
28               begin
29                    max:=0;
30                    for j:=i+1 to n do
31                        if (a[2,i]>a[2,j]) and (f[2,j]>max) then
32                           max:=f[2,j];
33                    f[2,i]:=max+1;
34               end;
35           max:=0;
36           for i:=1 to n do
37               if (max<f[1,i]) then
38                  max:=f[1,i];
39           for i:=1 to n do
40               if (max<f[2,i]) then
41                  max:=f[2,i];
42           writeln(max);
43      end;
44 end.