PAT1045. Favorite Color Stripe (30)(dp)

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

题意：

给出m中颜色作为喜欢的颜色（同时也给出顺序），然后给出一串长度为L的颜色序列，现在要去掉这个序列中的不喜欢的颜色，然后求剩下序列的一个子序列，使得这个子序列表示的颜色顺序符合自己喜欢的颜色的顺序，不一定要所有喜欢的颜色都出现

思路：

就是个简单的dp，一遍过，不过我dp不怎么样所以记录一下：

• 用dp[i][j]表示序列中第i个数并且喜欢的颜色在顺序中排j的最大值。
• 当num[i]是喜欢的颜色时，dp[i][j]=max{dp[i][k]，k<=j}+1
• 其他情况dp[i][j]=dp[i-1][j]

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<sstream>
#include<functional>
#include<algorithm>
using namespace std;
const int INF = 0xfffff;
const int maxn = 100050;int dp[10005][205];
int num[10005];
map<int, int> order;int main() {int n, m, l,t;	scanf("%d", &n);scanf("%d", &m);for (int i = 1; i <= m; i++) {scanf("%d", &t);order[t] = i;}scanf("%d", &l);for (int i = 1; i <= l; i++)scanf("%d", &num[i]);for (int i = 1; i <= l; i++) {if (order.find(num[i]) != order.end()) {int pos = order[num[i]];int max = -1,index=0;for (int j = 1; j <= pos; j++) {if (max < dp[i - 1][j]) {max = dp[i - 1][j];index = j;}}dp[i][pos] = dp[i - 1][index] + 1;for (int j = 1; j <= m&&j!=pos; j++) {dp[i][j] = dp[i - 1][j];}} else {for (int j = 1; j <= m; j++) {dp[i][j] = dp[i - 1][j];}}}int res = -1;for (int i = 1; i <= m; i++) {if (res < dp[l][i]) {res = dp[l][i];}}printf("%d", res);return 0;
}

这篇关于PAT1045. Favorite Color Stripe (30)(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---