pat 甲级 1045 Favorite Color Stripe

本文主要是介绍pat 甲级 1045 Favorite Color Stripe，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题使用动态规划（dp)的思想来解决。首先是状态的表示。f[i][j]为与所有公共子序列的集合的长度最大值。（p为主人公喜欢的子序列，s为题目给的序列）
状态计算：两种情况：
1. p[i] != s[j]

则p[i]与s[j]都不选或任选其一，分别为f[i-1][j-1],f[i][j-1],f[i-1][j]。又因为f[i-1][j-1]包含在f[i][j-1],f[i-1][j]中。所以f[i][j]=max(f[i−1][j],f[i][j−1])
 

2. p[i] == s[j]，则包含p[i]与s[j]。由于p[i]可以重复，f[i][j]=max(f[i][j−1],f[i−1][j−1])+1。f[i-1][j-1]+1表示p[i]之前未在中出现过的情况。f[i][j-1]+1则是p[i]已经在中出现过。

#include<iostream>
#include<cstring>using namespace std;
const int N=210,M=10010;int q[N],s[M];
int f[N][M];int main()
{int n,m,l;cin>>n;cin>>m;for(int i=1;i<=m;i++) cin>>q[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++){if(q[i]==s[j])f[i][j]=max(f[i][j-1],f[i-1][j-1])+1;else f[i][j]=max(f[i-1][j],f[i][j-1]);}cout<<f[m][l]<<endl;return 0;
}

这篇关于pat 甲级 1045 Favorite Color Stripe的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---