1 条题解

  • 0
    @ 2023-12-18 17:11:53

    这题还没有数据,但是代码还是可以写的,这道题其实就是很板的一道最长公共子序列,一道很经典的DP

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 2e4;
    char a[N],b[N];
    int dp[N][N];
    int main() {
    	int n,m;
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    	}
    	cin>>m;
    	for(int i=1;i<=m;i++){
    		cin>>b[i];
    	}
    	for(int i=1; i<=n; i++)
    		for(int j=1; j<=m; j++) {
    			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
    			if(a[i-1]==b[j-1])
    				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
    		}
    	int t=dp[n][m];
    	cout<<t;
    }
    
  • 1

信息

ID
1783
时间
1000ms
内存
256MiB
难度
10
标签
递交数
19
已通过
0
上传者