P1020 导弹拦截——动态规划 or 树状数组
Sleepy_Piggy
2018-02-11 16:13:18
### **嗯，这是一篇很认真的题解**
推荐一篇博客 [来自dalao的题解](https://butwedo.blog.luogu.org/solution-p2757) 为数不多的树状数组题解里面写的比较清楚的一篇。
- 题目有说明：“n方100分，nlogn200分” 这里两种做法都会讲到
第一问很明显是求**最长不上升子序列**，利用dp的思想，我们设f[i]为以第i个数为开头的最长不上升子序列的长度，然后可以得到这样一段程序
```cpp
for(int i=n;i>=1;i--){//注意！！因为它是以i开头的最长不上升子序列，所以这里要从n开始循环，不然会出现一些奇妙的bug
f[i]=1;//以第i个数为开头的最长不上升子序列的长度至少为1（当这个序列只有它本身这一个数）
for(int j=i+1;j<=n;j++){//用前面已经算好的来算现在正在算的这一个
if(a[j]<=a[i])//如果a[j]>a[i]的话就不满足不上升这个要求（毕竟a[j]在a[i]后面）
f[i]=max(f[i],f[j]+1); //更新f[i]~记得要+1啊
}
ans1=max(ans1,f[i]);//更新ans1
}
```
但是很明显，这段代码的时间复杂度是$O(n^2)$，没能达到$O(n logn)$
仔细想想，可以用树状数组啊ovo。用数值做下标，维护长度最大值，从后往前循环，每次查询之前已经放到树状数组里面的数中以这个数结尾的最长不上升子序列的长度的最大值，然后把这个最大值+1作为以自己结尾的最长不上升子序列的长度，放到树状数组里面。这不就很美滋滋了吗（手动滑稽）。详见代码：
```cpp
for(int i=n;i>=1;i--){//从后往前循环
int q=query(a[i])+1;//查询以小于等于x的数为开头的最长不上升子序列的长度的最大值
add(a[i],q);//这个最大值+1就是以当前这个数开头的最长不上升子序列的长度，丢到树状数组里面去
ans1=max(ans1,q);
}
printf("%d\n",ans1);
```
add和query在文末的完整代码中有
嗯就这样，第一问的时间复杂度就已经降到$O(n logn)$了
------------
第二问要用到一个Dilworth定理（Will爷万岁！！！）
_Dilworth定理：偏序集的最少反链划分数等于最长链的长度_
说简单点其实就是第二问相当于求**最长上升子序列**，很自然地又想到了dp。这次f[i]表示以i结尾的最长上升子序列的长度，然后就有了这样一段$O(n^2)$的代码
```cpp
for(int i=1;i<=n;i++){//同上，因为它是以i结尾的最长上升子序列，所以这里要从前往后，不然会出现一些奇妙的bug
f[i]=1;//以第i个数结尾的最长上升子序列的长度至少为1（当这个序列只有它本身这一个数）
for(int j=1;j<i;j++){
if(a[j]<a[i])//如果a[j]>=a[i]的话就不满足上升这个要求（毕竟a[j]在a[i]前面）
f[i]=max(f[i],f[j]+1);//更新f[i]~记得要+1啊
}
ans2=max(ans2,f[i]);//更新ans2
}
```
比较一下，是不是和第一问的dp代码很呢？
和第一问是一样的道理，如果要降到$O(n logn)$的复杂度，我们还是选择树状数组。用数值做下标，维护长度最大值，从前往后循环，每次查询之前已经放到树状数组里面的数中以这个数结尾的最长上升子序列的长度的最大值，然后把这个最大值+1作为以自己结尾的最长不上升子序列的长度，放到树状数组里面。代码：
```cpp
memset(f,0,sizeof(f));//还是memset一下比较保险
for(int i=1;i<=n;i++){//从前往后循环
int q=query(a[i]-1)+1;//查询以小于（没有等于！！！）x的数为结尾的最长上升子序列的长度的最大值
add(a[i],q);//这个最大值+1就是以当前这个数结尾的最长上升子序列的长度，丢到树状数组里面去
ans2=max(ans2,q);
}
```
------------
搞定辣！！！
完整代码：
- $O(n^2)$ dp
```
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ans1,ans2,f[100001],a[100001];
int main(){
while(scanf("%d",&a[++n])!=EOF);
n--;//要-1，不然n就不是正确的n了
for(int i=n;i>=1;i--){//注意！！因为它是以i开头的最长不上升子序列，所以这里要从n开始循环，不然会出现一些奇妙的bug
f[i]=1;//以第i个数开头的最长不上升子序列的长度至少为1（当这个序列只有它本身这一个数）
for(int j=i+1;j<=n;j++){//用前面已经算好的来算现在正在算的这一个
if(a[j]<=a[i])//如果a[j]>a[i]的话就不满足不上升这个要求（毕竟a[j]在a[i]后面）
f[i]=max(f[i],f[j]+1); //更新f[i]~记得要+1啊
}
ans1=max(ans1,f[i]);//更新ans1
}
for(int i=1;i<=n;i++){//同上，因为它是以i结尾的最长上升子序列，所以这里要从前往后，不然会出现一些奇妙的bug
f[i]=1;//以第i个数结尾的最长上升子序列的长度至少为1（当这个序列只有它本身这一个数）
for(int j=1;j<i;j++){
if(a[j]<a[i])//如果a[j]>=a[i]的话就不满足上升这个要求（毕竟a[j]在a[i]前面）
f[i]=max(f[i],f[j]+1);//更新f[i]~记得要+1啊
}
ans2=max(ans2,f[i]);//更新ans2
}
printf("%d\n%d\n",ans1,ans2);
}
```
- $O(n^2)$树状数组
```
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,maxn,ans1,ans2,f[1000001],a[1000001];
int lowbit(int x){return x&-x;}
void add(int x,int c){
for(int i=x;i<=maxn;i+=lowbit(i)) f[i]=max(f[i],c);//维护最大值
}
int query(int x){
int res=0;
for(int i=x;i>=1;i-=lowbit(i)) res=max(res,f[i]);//求以小于等于x的数为结尾的最长不上升子序列的长度的最大值
return res;
}
int main(){
while(scanf("%d",&a[++n])!=EOF) maxn=max(maxn,a[n]);
n--;//要-1，不然n就不是正确的n了
for(int i=n;i>=1;i--){//从后往前循环
int q=query(a[i])+1;//查询以小于等于x的数为开头的最长不上升子序列的长度的最大值
add(a[i],q);//这个最大值+1就是以当前这个数开头的最长不上升子序列的长度，丢到树状数组里面去
ans1=max(ans1,q);
}
printf("%d\n",ans1);
memset(f,0,sizeof(f));//还是memset一下比较保险
for(int i=1;i<=n;i++){//从前往后循环
int q=query(a[i]-1)+1;//查询以小于（没有等于！！！）x的数为结尾的最长上升子序列的长度的最大值
add(a[i],q);//这个最大值+1就是以当前这个数结尾的最长上升子序列的长度，丢到树状数组里面去
ans2=max(ans2,q);
}
printf("%d\n",ans2);
}
```