题目描述

传送门：P1020 导弹拦截

分析：第一问，很明显求最长不递增子序列，dp模板；第二问，则求不递增子序列的最少个数，根据dilworth定理，不递增子序列的最少个数=最长递增子序列的长度。即两问都是LIS问题。

Dilworth定理

若读者有一定离散基础并有兴趣的话，可直接看百度百科狄尔沃斯定理里的归纳法证明。若无离散和相关数学基础但也有兴趣的话，则推荐B站视频：[Dilworth定理] 洛谷 P1020 导弹拦截
以下给出笔者的一些粗陋想法：
每条不递增子序列都满足两个性质：下标递增且数值不递增。
假设已知有k条最长的不递增序列且除起点和终点外没有交点，那么当加入第j个数时(j=k+1)，枚举各序列末尾除重合终点外的数x1,x2…xk,若存在xi(1<=i<=k)不大于xj，那么xj就能加入该序列末尾（符合下标递增且数值不递增的性质），若不存在则说明xj必大于xi(i从1到k的所有值），而xj大于xi使最长递增序列的个数+1，此时只能把xj当作一条新的序列（或者说链）的起点，即每条（除重合起点外）链头的下标和数值都能在上一条中找到比它小的，符合递增子序列性质。
结论：
不递增子序列的最少个数=最长递增子序列的长度
不递减子序列的最少个数=最长递减子序列的长度

朴素dp(O(n^2))

定义dp[i]存储以a[i]结尾的最长不递增子序列的长度。可以想到每放一个a[i]就用j遍历0~i-1,若a[j]>=a[i],说明a[i]可放进a[j]后面，此时dp[i] = dp[j] + 1，因题目取最优解，每次遍历取最大值即可。
状态转移方程：dp[i] = max(dp[i],dp[j]+1)

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; int a[N]; int dp[N];//定义dp[i]=以a[i]结尾的最长不递增序列长度  int cnt; int main(){  while (cin>>a[cnt++]); for (int i=0;i<cnt-1;i++) dp[i] = 1; for (int i=0;i<cnt-1;i++){  for (int j=0;j<i;j++){  if (a[i]<=a[j]) dp[i] = max(dp[i],dp[j]+1); //若符合不递增性质，状态转移 } } int ans = -1; for (int i=0;i<cnt-1;i++){  //printf("dp[%d] = %d\n",i,dp[i]); ans = max(dp[i],ans); //最后答案取最大值 } cout<<ans<<endl; //求最长递增同理 for (int i=0;i<cnt-1;i++) dp[i] = 1; for (int i=0;i<cnt;i++){  for (int j=0;j<i;j++){  if (a[i]>a[j]) dp[i] = max(dp[i],dp[j]+1); } } ans = -1; for (int i=0;i<cnt;i++) ans = max(dp[i],ans); cout<<ans<<endl; } 

二分/O(nlogn)

朴素dp套了双层循环，时间复杂度O(n^2)
而题目数据范围为1e5,O(n^2)显然是不可行的，考虑nlog(n)做法
假若在i之前已经有序列A满足不递增性质，发现a[i]是否加入序列只和序列A末尾值有关，即前面的数不会对当前决策有影响。如果a[i]小于等于末尾值，直接放到末尾，序列长度加一；而如果大于，则通过二分去找第一个比a[i]小的数的位置pos，而这个位置是a[i]在序列的最优位置，因a[i]比a[t]大，那么后来的数接到a[i]后面一定比a[t]的决策更优，所以将a[t]替换成a[i]。

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; int a[N]; int dp[N];//dp[i]用来存当前LIS序列末尾值  int cnt; int main(){  while (cin>>a[++cnt]); dp[1] = a[1]; int len = 1; for (int i=2;i<cnt;i++){ //求最长不递增子序列  if (dp[len]>=a[i]) dp[++len] = a[i];//如果末尾值比a[i]大，直接放入 else { //如果末尾值比a[i]小，查找替换  int pos = upper_bound(dp+1,dp+len+1,a[i],greater<int>()) - dp; //二分查找第一个小于a[i]的位置 dp[pos] = a[i]; } } //for (int i=1;i<cnt;i++) printf("dp[%d] = %d\n",i,dp[i]); cout<<len<<endl; len = 1; memset(dp,0,sizeof(dp)); dp[1] = a[1]; for (int i=2;i<cnt;i++){ //求最长递增子序列  if (dp[len]<a[i]) dp[++len] = a[i];//如果末尾值比a[i]小，直接放入 else { //如果末尾值不比a[i]小，查找替换  int pos = lower_bound(dp+1,dp+len+1,a[i]) - dp; //二分查找第一个大于等于a[i]的位置 dp[pos] = a[i]; } } cout<<len<<endl; } 

桶优化/O(n^2)

取maxi为a[]数组的最大值 ，想象有标号依次为1-maxi的桶，
定义f[j]（1<=j<=maxi)为以数i结尾的最长递增序列长度
每当查询a[i]前面有多少数时，遍历前面的1~a[i],取x = max(f[j])+1(1<=j<a[i]),x即为以a[i]结尾的最长子序列长度
同时遍历a[i]+1~maxi的桶，若该桶的值比x小，则
将其赋值为x。
状态转移方程：f[j] = max(f[j],x) (a[i]+1<=j<=maxi)
最长不递增子序列同理

#include <bits/stdc++.h> using namespace std; int cnt,maxi; const int N = 5e4 + 7; const int M = 1e5 + 7; int ans1,ans2; int f[N]; int a[M]; int main(){  while (cin>>a[cnt++]) maxi = max(a[cnt-1],maxi); cnt--; for (int i=0;i<cnt;i++){ //最长不递增  int r = 0; for (int j=a[i];j<=maxi;j++) r = max(r,f[j]); ans1 = max(ans1,r+1); for (int j=a[i];j;j--) f[j] = max(f[j],r+1); } memset(f,0,sizeof(f)); for (int i=0;i<cnt;i++){ //最长递增  int r = 0; for (int j=a[i];j;j--) r = max(r,f[j]); ans2 = max(ans2,r+1); for (int j=a[i]+1;j<=maxi;j++) f[j] = max(f[j],r+1); } cout<<ans1<<endl<<ans2<<endl; } 

时间复杂度依然是O（n^2),发现f[]数组的计数结构可用树状数组维护。

树状数组优化

其本质就是桶优化
只是树状数组提高了查找和更新的效率。

#include <bits/stdc++.h> using namespace std; const int N = 5e4 + 7; const int M = 1e5 + 7; int t[N],a[M]; int cnt,ans1,ans2,maxx; int lowbit(int x){  return x & -x; } int ask(int i){  int maxi = 0; for (;i<=maxx;i+=lowbit(i)) maxi = max(t[i],maxi); return maxi; } void update(int i,int k){  for (;i;i-=lowbit(i)) t[i] = max(t[i],k); } int query(int i){  int maxi = 0; for (;i;i-=lowbit(i)) maxi = max(t[i],maxi); return maxi; } void change(int i,int k){  for (;i<=maxx;i+=lowbit(i)) t[i] = max(t[i],k); } int main(){  while (cin>>a[cnt++]) maxx = max(maxx,a[cnt-1]); cnt--; for (int i=0;i<cnt;i++){ //求最长不递增 int x = ask(a[i]) + 1; ans1 = max(x,ans1); update(a[i],x); } memset(t,0,sizeof(t)); for (int i=0;i<cnt;i++){ //求最长递增 int x = query(a[i]) + 1; ans2 = max(x,ans2); change(a[i]+1,x);//注意这里要a[i]+1 } cout<<ans1<<endl<<ans2<<endl; } 

线段树优化

待补充