POJ 1887 Testing the CATCHER.

POJ 1887 Testing the CATCHER.

~~~~

求最長不上升子序列，把數組倒過來不就是求最長上升子序列了麼，QAQ..

~~~~

#include
#include
#include
#include
#define N 10000
using namespace std;

int f[N],a[N];
int main()
{
    int t,c,T=0;
    while(~scanf(%d,&t),t!=-1)
    {
        c=0;
        a[c++]=t;
        while(~scanf(%d,&t),t!=-1)
            a[c++]=t;
        int i,j;
        for(i=0,j=c-1;if[cnt]) f[++cnt]=a[k];
                else
                {
                    int pos=lower_bound(f+1,f+cnt,a[k])-f;
                    f[pos]=a[k];
                }
            }
        }
        printf(Test #%d:
,++T);
        printf(  maximum possible interceptions: %d

,cnt);
    }
    return 0;
}