1 条题解
-
0李远臻 (liyuanzhen) LV 6 @ 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
- 上传者