首页 > 代码库 > PAT 甲级 1045 Favorite Color Stripe（DP）
PAT 甲级 1045 Favorite Color Stripe（DP）
题目链接 Favorite Color Stripe
题意：给定A序列和B序列，你需要在B序列中找出任意一个最长的子序列，使得这个子序列也是A的子序列
（这个子序列的相邻元素可以重复）
只要求出这个子序列长度的最大值即可
很基础的DP题，设f[i]为当前以a[i]结尾的子序列的长度的最大值，扫描B序列的每个元素时实时更新即可。
#include <bits/stdc++.h>using namespace std;#define rep(i, a, b) for (int i(a); i <= (b); ++i)#define dec(i, a, b) for (int i(a); i >= (b); --i)typedef long long LL;const int L = 10010;const int N = 210;int a[L], c[N], f[N];vector <int> v[N];int n, m, l;int ans;int main(){ scanf("%d%d", &n, &m); rep(i, 1, m){ scanf("%d", c + i); v[c[i]].push_back(i); } scanf("%d", &l); rep(i, 1, l) scanf("%d", a + i); rep(i, 1, l){ for (auto u : v[a[i]]){ if (f[u]) ++f[u]; rep(j, 0, u - 1) f[u] = max(f[u], f[j] + 1); } } rep(i, 1, m) ans = max(ans, f[i]); return 0 * printf("%d\n", ans);}
PAT 甲级 1045 Favorite Color Stripe（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。