AcWing 1529. 最佳彩色带
原题链接
中等
最佳彩色带
- 这道是最长公共子序列的变形。这里因为同一个数字可以选择多次,因此只要把最长公共子序列的代码的
if (a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)
改成 if (a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i][j - 1] + 1)
就可以通过。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 10010;
int a[N], b[N], dp[N][N];
int main()
{
int T;
cin >> T;
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] == b[j]) dp[i][j] = max(dp[i][j], dp[i][j - 1] + 1);
}
cout << dp[n][m];
return 0;
}