题解 P1020 【导弹拦截】
「已注销」
2017-11-09 17:41:53
#n方200分的题解！
只是加了一个常数优化,最坏1/2 n^2，平均效率较高
在朴素n^2算法中,用f[i]储存以i结尾的最长不上升子序列长度，如样例
i 1 2 3 4 5 6 7 8
a 389 207 155 300 299 170 158 65
f 1 2 3 2 3 4 5 6
发现当f的值相同时，越后面的导弹高度越高
用d[i]维护f值为i的最后一个导弹的位置，t记录当前已经求出最长不升子序列长度
递推求f时枚举a[d[t]]，a[d[t-1]]，。。。，a[d[1]]是否≥当前求的导弹高度，是就更新f
然后根据某定理求出第二问（楼下大佬们说的很清楚）
```cpp
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n=0,a[100001],f[100001],d[100001],ans=1,t=0;
int main() {
while(~scanf("%d",&a[++n]));//读入数据方法
n--;//n是导弹数，由于某些原因要--
for(int i=1; i<=n; i++) {
f[i]=1;
for(int j=t; j>0; j--)
if(a[i]<=a[d[j]]) {
f[i]=f[d[j]]+1;
break;
}
t=max(t,f[i]);
d[f[i]]=i;//简单的维护过程
ans=max(ans,f[i]);
}
printf("%d\n",ans);
ans=1;
t=0;
for(int i=1; i<=n; i++) {
f[i]=1;
for(int j=t; j>0; j--)
if(a[i]>a[d[j]]) {
f[i]=f[d[j]]+1;
break;
}
t=max(t,f[i]);
d[f[i]]=i;
ans=max(ans,f[i]);
}
printf("%d",ans);
}
```