【动态规划】线性dp——LIS和LCS

参考文章

子序列

一个序列$A＝a_1,a_2,\dots ,a_n$ 中任意删除若干项，剩余的序列叫做 A 的一个子序列。也可以认为是从序列 A 按原顺序保留任意若干项得到的序列。（例如：对序列｛1,3,5,4,2,6,8,7｝来说，序列｛3,4,8,7｝是它的一个子序列。）

LIS 最长上升子序列

代码

转移方程：$dp[i]=max(dp[i],dp[j]+1)$

O(n2)

const int N=5010;
int n;
int a[N],dp[N],ans;
signed main(){cin>>n;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0;i<n;i++){dp[i]=1;//自己是一个数列for(int j=0;j<i;j++){if(a[i]>a[j]){//上升dp[i]=max(dp[i],dp[j]+1);//找之前的数列ans=max(dp[i],ans);}}}cout<<ans<<endl;return 0;
}

O(nlogn)

//O(nlogn)做法 
//下降序列
int ans=1,dp[N]={0};
dp[1]=a[1];
for(int k=2;k<=i;k++){if(a[k]<=dp[ans]){//更小的向后取组成序列ans++;dp[ans]=a[k];//下降的序列}else{//跟最后的比不下降 就放前面相当于重开一个序列//dp下降 用greater<>int j=upper_bound(dp+1,dp+1+ans,a[k],greater<int>())-dp;//二分 找第一个小于a[k]的数dp[j]=a[k];//开下降序列}
}
//上升序列
int ans=1,dp[N]={0};
dp[1]=a[1];
for(int k=2;k<=i;k++){if(a[k]>dp[ans]){ans++;dp[ans]=a[k];}else{//dp上升int j=upper_bound(dp+1,dp+1+ans,a[k])-dp;//二分 找第一个大于a[k]的数dp[j]=a[k];}
}

例题

P1020 导弹拦截

构造下降序列找导弹数目，上升序列找系统数目。
二分查找 O(nlogn)做法
细节见代码。

signed main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);int i=1;while(cin>>a[i])i++;i--;//能拦截多少导弹int ans=1;dp[1]=a[1];for(int k=2;k<=i;k++){if(a[k]<=dp[ans]){//每一发炮弹都不能高于前一发的高度//比前一发低，记录数目ans++;dp[ans]=a[k];//构造一个下降的序列}else{//dp下降int j=upper_bound(dp+1,dp+1+ans,a[k],greater<int>())-dp;//二分 找第一个小于a[k]的数 相当于新开一个系统 新开一个下降序列dp[j]=a[k];//开下降序列}}cout<<ans<<endl;//用多少系统int cnt=1;x[1]=a[1];for(int k=2;k<=i;k++){if(x[cnt]<a[k]){//新开一个系统cnt++;x[cnt]=a[k];//x是上升序列}else{int j=lower_bound(x+1,x+cnt+1,a[k])-x;//找第一个大于等于a[k]的系统 能拦截这个炮弹x[j]=a[k];}// for(int m=1;m<=cnt;m++)cout<<x[m]<<' ';// cout<<endl;}cout<<cnt;return 0;
}

P2782 排序+LIS

const int N=2e5+10;
struct fr{int a,b;
}c[N];
int dp[N];
void solve(){int n;cin>>n;forr(i,1,n){cin>>c[i].a>>c[i].b;}sort(c+1,c+1+n,[](fr x,fr y){return x.a<y.a;});//找LISint ans=1;/*//超时forr(i,1,n){dp[i]=1;forr(j,1,i-1){if(c[i].b>c[j].b){dp[i]=max(dp[i],dp[j]+1);ans=max(dp[i],ans);}}}*/dp[1]=c[1].b;forr(i,2,n){if(c[i].b>dp[ans]){ans++;dp[ans]=c[i].b;}else{int j=upper_bound(dp+1,dp+ans+1,c[i].b)-dp;//替换第一个大于c[i].b的dp[j]=c[i].b;}}cout<<ans<<endl;
}

P1091 两次LIS

const int N=2e5+10;
int dp[N],dpr[N];
void solve(){int n;cin>>n;vector<int>t(n+1);forr(i,1,n){cin>>t[i];}int maxn=0;forr(i,1,n){// dp[i]=1;forr(j,1,i-1){if(t[i]>t[j])dp[i]=max(dp[j]+1,dp[i]);}}reforr(i,1,n){// dpr[i]=1;reforr(j,i+1,n){if(t[i]>t[j])dpr[i]=max(dpr[j]+1,dpr[i]);}}forr(i,1,n){// cout<<dp[i]<<' '<<dpr[i]<<' '<<dp[i]+dpr[i]<<endl;maxn=max(dp[i]+dpr[i]+1,maxn);}cout<<n-maxn<<endl;
}

LCS 最长公共子序列

代码

状态转移方程$dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1)$，dp是LCS的长度。

forr(i,1,len){forr(j,1,len){if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}
}

例题

P1435

const int N=1e3+10;
int dp[N][N];
void solve(){string s;cin>>s;string rs=string(s.rbegin(),s.rend());int len=s.size();forr(i,1,len){forr(j,1,len){if(s[i-1]==rs[j-1])dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}cout<<len-dp[len][len];
}

LCIS 最长公共上升子序列

模板题

状态转移方程：

两重循环i、j分别遍历a、b数组，另有一个k，O(n3)。

• $a[i]\ne b[j]$：确定$i$后，每次遍历$j$，从上一个确定的$dp[i-1][j]$转移过来
• $a[i]=b[j]$：如果相等，从$b[j]>b[k]$的$k$位置+1，找最大值

优化

k遍历的是$1\le k\le j-1$，可以在遍历j的同时更新$max(dp[i-1][j])$用到j+1的更新中
参考文章

//优化前for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j) {f[i][j] = f[i - 1][j];      // 枚举所有不包含a[i]的上升公共子序列if (a[i] == b[j]) {f[i][j] = max(f[i][j], 1);      // 更新空集for (int k = 1; k < j; ++k) if (b[k] < b[j])            f[i][j] = max(f[i][j], f[i][k] + 1);}}
//原文链接：https://blog.csdn.net/yl_puyu/article/details/109781829//优化后
forr(i,1,n){//对a数组每一个数int val=0;forr(j,1,m){//跟b数组中匹配 以b[j]为结尾dp[i][j]=dp[i-1][j];//从上一个a中的数转移过来//是公共序列if(a[i]==b[j])dp[i][j]=max(val+1,dp[i][j]);//优化  b[j]<a[i]相当于b[1...j-1]<b[j]if(b[j]<a[i])val=max(dp[i-1][j],val);//更新最大值}
}
int ans=0,ansj;
forr(j,1,m){if(ans<dp[n][j])ans=dp[n][j],ansj=j;
}
cout<<ans;

再加记录序列：
但是提交之后一直RE 卡了一小时 不知道哪里出问题了

const int N=510;
int dp[N];
int a[N],b[N];
vector<int>sq[N];
void solve(){int n,m;cin>>n;forr(i,1,n)cin>>a[i];cin>>m;forr(i,1,m){cin>>b[i];// sq[i]=vector<int>();}forr(i,1,n){//对a数组每一个数// int val=0;int mj=0;forr(j,1,m){//跟b数组中匹配//优化  b[j]<a[i]相当于b[1...j-1]<b[j]//dp保持j-1状态if(b[j]<a[i]&&dp[j]>dp[mj]){// val=max(dp[i-1][j],val);//更新最大值// val=dp[j];mj=j;}// dp[i][j]=dp[i-1][j];//从上一个a中的数转移过来//以b[j]为结尾 是公共序列if(a[i]==b[j]){dp[j]=max(dp[mj]+1,dp[j]);sq[j]=sq[mj];sq[j].push_back(b[j]);}}}int ans=0,ansj=1;forr(j,1,m){if(dp[ansj]<dp[j])ans=dp[j],ansj=j;}cout<<dp[ansj]<<endl;forr(i,0,sq[ansj].size()-1){cout<<sq[ansj][i]<<' ';}
}

让豆包改了之后这样：

void solve() {int n, m;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];}cin >> m;vector<int> b(m + 1);vector<int> dp(m + 1, 0);vector<vector<int>> sq(m + 1);for (int i = 1; i <= m; i++) {cin >> b[i];}for (int i = 1; i <= n; i++) {int mj = 0;for (int j = 1; j <= m; j++) {if (b[j] < a[i] && dp[j] > dp[mj]) {mj = j;}if (a[i] == b[j]) {if (dp[mj] + 1 > dp[j]) {dp[j] = dp[mj] + 1;sq[j] = sq[mj];sq[j].push_back(b[j]);}}}}int ans = 0, ansj = 1;for (int j = 1; j <= m; j++) {if (dp[ansj] < dp[j]) {ans = dp[j];ansj = j;}}cout << dp[ansj] << endl;for (int i = 0; i < sq[ansj].size(); i++) {cout << sq[ansj][i] << ' ';}cout << endl;
}