当前位置：网站首页>最长上升子序列模型 AcWing 272. 最长公共上升子序列

最长上升子序列模型 AcWing 272. 最长公共上升子序列

2022-07-27 10:35:00 【T_Y_F666】

最长上升子序列模型 AcWing 272. 最长公共上升子序列

原题链接

AcWing 272. 最长公共上升子序列

算法标签

动态规划线性DP 前缀和

思路

在这里插入图片描述

上述思路代码

#include<bits/stdc++.h>
// 若将int定义为long long 产生Memory Limit Exceeded错误 
// #define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 3005;
int a[N], b[N];
// f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合；
// f[i][j]的值等于该集合的子序列中长度的最大值；
int f[N][N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n=read();
	rep(i, 1, n+1){
	    a[i]=read();
	}
	rep(i, 1, n+1){
	    b[i]=read();
	}
	rep(i, 1, n+1){
	    int mx=1;
	    rep(j, 1, n+1){
	        f[i][j]=f[i-1][j];
	        // 满足公共子序列
	        if(a[i]==b[j]){
	            rep(k, 1, j){
	                if(b[k]<b[j]){
	                    f[i][j]=max(f[i][j], f[i][k]+1);
	                }
	            }    
	        }
	    }
	}
	int res=0;
	rep(i, 1, n+1){
	    res=max(res, f[n][i]);
	} 
	printf("%d", res);
	return 0;
}

由于每次循环求得的mx是满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值。因此可以直接将maxv提到第一层循环外面，减少重复计算，此时只剩下两重循环。
最终答案枚举子序列结尾取最大值即可。

代码

#include<bits/stdc++.h>
// #define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 10005;
int a[N], b[N];
// f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合；
// f[i][j]的值等于该集合的子序列中长度的最大值；
int f[N][N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n=read();
	rep(i, 1, n+1){
	    a[i]=read();
	}
	rep(i, 1, n+1){
	    b[i]=read();
	}
	rep(i, 1, n+1){
	    int mx=1;
	    rep(j, 1, n+1){
	        // 不包含a[i]的子集，最大值是f[i - 1][j]
	        f[i][j]=f[i-1][j];
	        // 满足公共子序列 即既包含a[i] 也包含b[j]
	        if(a[i]==b[j]){
	            f[i][j]=max(f[i][j], mx);
	        }
	        // 满足上升子序列
	        if(a[i]>b[j]){
	            mx=max(mx, f[i-1][j]+1);
	        }
	    }
	}
	int res=0;
	rep(i, 1, n+1){
	    res=max(res, f[n][i]);
	} 
	printf("%d", res);
	return 0;
}