dp基础：poj1887

题目

最长不上升子序列

Input

所有输入数据都是非负整数，且小于等于32767。每组数据最后一个数为-1。保证每组数据数量大小不超过1e5

Output

每个测试的输出包括一个测试编号以及答案（具体看样例）。每组样例中间有一个空行

Examples

Input

389
207
155
300
299
170
158
65
-1
23
34
21
-1
-1

Output

Test #1:
 maximum possible interceptions: 6

Test #2:
 maximum possible interceptions: 2

代码

#include<stdio.h>
int num[50000],len;/*num为dp数组，其中的数组地址的值表示长度，而其对应的值表示该长度下的序列末尾数值的最小值*/
int solve(int k)/*二分，由于之前的序列都是采用的最优解，所以说长度越长末尾的数就越小，不然则反之利用这一规律用二分来减少时间复杂度*/
{
    int r=len,l=1,mid;
    while(r>l)
    {
       mid=(r+l)/2;
       if(num[mid]>=k)/*要num[mid]小于k时k才能成为长度为mid时序列的最后项*/
       {
           l=mid+1;
       }
       else
       r=mid;
    }
    return r;
}
int main()
{
    int k,t=1;
    //freopen("F:/y.txt","r",stdin);
    while(~scanf("%d",&k)&&k!=-1)
    {
       len=1;
       num[len]=k;
       while(~scanf("%d",&k)&&k!=-1)
       {
           if(num[len]>=k)/*如果该长度下的序列末尾数值比k大，则该序列长度加一末尾数值变成成k*/
           {
              num[++len]=k;
           }
           else/*而如果小于k则用二分法更新之前序列的末尾值以便于之后容纳更多的数字且最大长度不会增加*/
           {
              num[solve(k)]=k;
           }
       }
       if(t!=1)
       printf("\n");
       printf("Test #%d:\n",t++);
       printf("  maximum possible interceptions: %d\n",len);
    }
    return 0;
 }