AcWing 1529. 最佳彩色带
原题链接
中等
作者:
sy123
,
2021-01-05 21:21:01
,
所有人可见
,
阅读 436
暴力DP
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N],b[210];
int dp[N];
int n,m,k;
int main(){
cin>>n;
cin>>m;
for(int i=1;i<=m;i++)cin>>b[i];
cin>>k;
for(int i=1;i<=k;i++)scanf("%d",&a[i]);
for(int i=1;i<=k;i++){
bool flag=false;
for(int j=1;j<=m;j++){
if(a[i]==b[j]){
a[i]=j;//赋予权值
flag=true;
break;
}
}
if(flag==false)a[i]=10000;//不喜欢的颜色赋予最大值,不考虑
}
if(a[1]<=m)dp[1]=1;
int maxv=dp[1];
for(int i=2;i<=k;i++){
if(a[i]<=m){//是合法颜色
dp[i]=1;//合法颜色的长度最短为1,前面都是不合法的
for(int j=1;j<i;j++){
if(a[j]<=a[i]&&(dp[j]+1>dp[i])&&a[j]<=m){
dp[i]=dp[j]+1;
}
}
maxv=max(maxv,dp[i]);
}
}
cout<<maxv<<endl;
return 0;
}
#include <iostream>
using namespace std;
const int N = 210, M = 10010;
int n, m, l;
int p[N], s[M];
int f[N][M];//f[i][j]表示p[1]到p[i]和s[1]到s[j]最大公共部分
int main()
{
cin >> n;
cin >> m;
for (int i = 1; i <= m; i ++ ) cin >> p[i];
cin >> l;
for (int i = 1; i <= l; i ++ ) cin >> s[i];
for (int i = 1; i <= m; i ++ )
for (int j = 1; j <= l; j ++ )
{
f[i][j] = max(f[i - 1][j],f[i][j-1]);
//f[i][j - 1]+1不能写成f[i - 1][j - 1]+1,因为比如3 5和3 5 5
if (p[i] == s[j]) f[i][j] = max(f[i][j], f[i][j - 1] + 1);
}
cout << f[m][l] << endl;
return 0;
}