题目链接

拦截导弹

题目思路

第一问dp求解
第二问dilworth定理
Dilworth定理
简单来说：

一个序列的最长递增子序列的长度 等于 这个序列的最长不递增（包含递减和相等）子序列的个数和；

相反，

一个序列的最长递减子序列的长度 等于 这个序列的最长不递减（包含递增和相等）子序列的个数和；

代码实现

#include<bits/stdc++.h>
using namespace std;
const int Max=1e5;
int a[Max],num=0,dp[Max],ans=0;
int main()
{
    while(cin>>a[++num]);
    num--;
    dp[1]=1;
    for(int i=2;i<=num;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[i]<=a[j]) dp[i]=max(dp[i],dp[j]+1);

        }
        ans=max(ans,dp[i]);
    }
//    cout<<num<<endl;
//    for(int i=1;i<=num;i++)
//        cout<<dp[i]<<' ';
    cout<<ans<<endl;
    memset(dp,0,sizeof dp);
    ans=0;
    dp[1]=1;
    for(int i=2;i<=num;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}