题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1257
一开始本来是这么想的，就是求普通的最长下降子序列，保存在d[i]，也就是前i位最长子序列
然后遍历所有的d[i]，数量最多的数字就是答案，比如例题中的 d[]是 1 2 3 2 3 4 5 6
2还有1 有两个，所以答案是2
但是不知道为什么WR
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000+5;
int n[maxn],d[maxn],cnt[maxn];
int main()
{int N; while(scanf("%d",&N)!=EOF){for(int i=0;i<N;i++){scanf("%d",&n[i]);d[i]=1;for(int j=0;j<i;j++)if(n[j]>=n[i]) d[i]=max(d[i],d[j]+1); }int ans=0;memset(cnt,0,sizeof(cnt));for(int i=0;i<N;i++){cnt[d[i]]++;ans=max(ans,cnt[d[i]]);}cout<<ans<<endl;}return 0;
}
想的是每次遇到一个比当前拦截系统的高度要高的导弹时，就重新开一个拦截系统。这并没有完全利用拦截系统。正确的思路：保存下所有拦截系统当前所能发射的最高高度，当遇到一个导弹时，选择距离它高度最近的拦截系统去拦截！从前往后扫就保证了这一点。 ——墨温温的博客
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000+5;
int d[maxn]; //d[i] 保存当前拦截系统最高的高度
int main()
{int N,h,j; while(scanf("%d",&N)!=EOF){int num=0;d[num++]=0x3f3f3f3f;for(int i=0;i<N;i++){scanf("%d",&h);for(j=0;j<num;j++)if(h<d[j]){d[j]=h;break;} if(j>=num) d[num++]=h; } cout<<num<<endl;}return 0;
}