- 【模板】最长公共子序列
50分做法
- 2024-7-19 16:41:38 @
#include<bits/stdc++.h>
using namespace std;
// 定义变量和数组
int n,a[1005],b[1005],dp[1005][1005];
int main(){
// 读入序列的长度
cin >> n;
// 输入第一个序列
for (int i=1; i<=n;i++){
cin >> a[i];
}
// 输入第二个序列
for(int i=1; i<=n;i++){
cin >> b[i];
}
// 动态规划求解最长公共子序列的长度
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
// 如果两个序列当前位置的元素相等
if(a[i]==b[j]){
// dp[i][j] 存储的是序列 a 的前 i 个元素与序列 b 的前 j 个元素的最长公共子序列的长度
dp[i][j]=dp[i-1][j-1]+1;
}else{
// 如果元素不相等,dp[i][j] 取 dp[i-1][j] 和 dp[i][j-1] 中的较大值
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
// 输出最长公共子序列的长度
// dp[n][n] 包含的是整个序列 a 和 b 的最长公共子序列的长度
cout << dp[n][n];
return 0;
}
满分做法思路不大一样
1 条评论
-
112126zcg 小猫牢底 LV 7 (10153/11178) @ 2024-7-19 17:46:26
666666666666666666666666666666666666666666
- 1
信息
- ID
- 433
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 8
- 已通过
- 5
- 上传者