一維的動(dòng)態(tài)，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1887
#include <stdio.h>

const int LEN = 10001;

int num[LEN];

int dp[LEN];

int los ( int n )
{

    dp[n-1] = 1;
    for ( int i=n-2; i>=0; i-- )
    {
        int max = 0;
        for ( int j=i+1; j<n; j++ )
        {
            if ( dp[j] > max && num[j] < num[i] )
            {
                max = dp[j];
            }
        }
        dp[i] = max + 1;
    }

    int maxest = 0;
    for ( i=0; i<n; i++ )
    {
        if ( dp[i] > maxest )
        {
            maxest = dp[i];
        }
    }

    return maxest;
} 

int main ()
{
    int in;
    int count = 0;

    while ( scanf ( "%d", &in ) != EOF && in != -1 )
    {
        num[0] = in;
        int n = 1;
        while ( scanf ( "%d", &in ) != EOF && in != -1 )
        {
            num[n++] = in;
        }
        printf ( "Test #%d:\n  maximum possible interceptions: %d\n\n", ++count, los ( n ) );
    }
    return 0;
}