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

缺乏、安全感 2023-09-28 14:26 39阅读 0赞

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

### 原题链接 ###

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

### 算法标签 ###

动态规划 线性DP 前缀和

### 思路 ###

![在这里插入图片描述][f3cf547e33634d7f809fa945c2794333.png]

#### 上述思路代码 ####

#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;
    }

### tips ###

产生Memory Limit Exceeded错误 ， 可能是由该语句导致

define int long long

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 272.]: https://www.acwing.com/problem/content/274/
[f3cf547e33634d7f809fa945c2794333.png]: https://img-blog.csdnimg.cn/f3cf547e33634d7f809fa945c2794333.png
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png