学步园

经典例题：PKU 1887 Testing the CATCHER

http://acm.pku.edu.cn/JudgeOnline/problem?id=1887

解题思路:创建一个一维数组num_array[j]，max_array[],num_array[j]表示序列的元素，max_array[i]表示以第i个元素结尾的序列中的最长下降子序列，初始化为0，对于一个max_array[i]，遍历前面的每个元素j，如果num_array[j]> num_array[i]且max_array[j]>= max_array[i],那么max_array[j]就要加1，所以递推公式为：

if(num_array[i]<=num_array[j]&&max_array[i]<=max_array[j])  max_array[i]++;

最后选最大的一个max_array[i]就是最长下降子序列的个数。

#include <iostream><br /> using namespace std;<br /> int a[5005];<br /> int maxa[5005];<br /> int main()<br /> {<br /> int i,j,k,n,m,t;<br /> int cnt =0;<br /> while (scanf("%d",&a[0])!=EOF)<br /> {<br /> cnt++;<br /> if (a[0] == -1)<br /> {<br /> break;<br /> }</p> <p> i = 1;<br /> while (scanf("%d",&a[i]))<br /> {<br /> if (a[i] == -1)<br /> {<br /> break;<br /> }<br /> i++;<br /> }<br /> //----------------------------------------------<br /> int len = i;<br /> int maxnum = -1;<br /> for (i=0;i<=len;i++)<br /> maxa[i] = 0;<br /> for (i=1;i<=len;i++)<br /> {<br /> for (j=0;j<i;j++)<br /> {<br /> if (a[i]<=a[j] && maxa[i]<=maxa[j]) //理解这句 maxa[i]<=maxa[j]<br /> {<br /> maxa[i]++;<br /> }<br /> }<br /> maxnum = maxnum>maxa[i]?maxnum:maxa[i];<br /> }<br /> printf("Test #%d:/n maximum possible interceptions: %d/n/n",cnt,maxnum);<br /> }<br /> return 0;<br /> }