AcWing 1010. 拦截导弹

AcWing 1010. 拦截导弹

这个题是真的太神奇了，数学证明出来的性质（Dilworth定理）：
“能覆盖整个序列的最少的不上升子序列的个数”等价于“该序列的最长上升子序列长度”
同理即有：
“能覆盖整个序列的最少的不下降子序列的个数”等价于“该序列的最长下降子序列长度”

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
int a[N];
int f[N];

int main(){
    int n=0;
    int res=0;
    while(cin>>a[n])n++; 
    
    for(int i=0;i<n;i++){
        f[i]=1;
        for(int j=0;j<i;j++){
            if(a[i]<=a[j])
                f[i]=max(f[i],f[j]+1);
        }
        res=max(res,f[i]);
    }
    
    cout<<res<<endl;
    
    res=0;
    for(int i=0;i<n;i++){
        f[i]=1;
        for(int j=0;j<i;j++){
            if(a[i]>a[j])
                f[i]=max(f[i],f[j]+1);
        }
        res=max(res,f[i]);
    }
    cout<<res<<endl;
    
    return 0;
}
```z