题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805437411475456
一开始没看懂题目，后来发现给出的喜欢的颜色的排序很重要，因为最后得到的最长的stripe的颜色顺序也要于此一致，换句话说，最后的stripe喜欢颜色程度是非递增的。
暴力遍历子列用脚趾头想都知道会超时，那么自然想到动态规划。但这题是如何状态转移的没有搞清楚，因为我害怕出现这样的情况：现在的最长序列一直无法和新加进来的元素拼接，也就是stipe长度一直没有增长。但慢慢地，那些被丢掉的元素如果拼接起来，里面可能存在更长的满足条件的stripe。
但我忽略了这样一个事实：如果后面丢弃元素拼接起来存在更长的序列的话，前面也有可能存在能够拼到后面这个更长序列里的元素，因为只要让序列是非递增的就好了。比如喜欢序列为{2,3,1,5,4}，后面序列为{2,...}，前面序列为{2,3,3,1}，那么只要把前面的2拼到后面就好了。
那么我们所取的dp数组就有明确意义了：dp[i]表示的是从0到i，满足条件的最长stripe的长度。
下面是完整代码
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;int main() {
int N, M, L;cin >> N;cin >> M;vector<int> pri(N + 1, 0);for (int i = 0; i < M; i++) {
int color;cin >> color;pri[color] = M - i;}cin >> L;vector<int> stripe;stripe.clear();for (int i = 0; i < L; i++) {
int tmp;cin >> tmp;if (pri[tmp] > 0) {
stripe.push_back(tmp);}}vector<int> dp(stripe.size(), 1);int max_len = 1;for (int i = 0; i < stripe.size(); i++) {
for (int j = 0; j < i; j++) {
if (pri[stripe[j]] >= pri[stripe[i]]) {
dp[i] = max(dp[i], dp[j] + 1);}}max_len = max(max_len, dp[i]);}cout << max_len;return 0;
}
我对颜色排序的表示是用颜色的priority来表示，最前面的颜色优先级最高，为M，之后的颜色递减1。不是喜欢的颜色就为0。
vector<int> pri(N + 1, 0);for (int i = 0; i < M; i++) {
int color;cin >> color;pri[color] = M - i;}
当然还是有参考柳神代码，对序列做了预处理，把不在喜欢列表里的元素（颜色）都先去掉。
cin >> L;vector<int> stripe;stripe.clear();for (int i = 0; i < L; i++) {
int tmp;cin >> tmp;if (pri[tmp] > 0) {
stripe.push_back(tmp);}}
接下来是dp环节。对每一个i，遍历其前面的位置j，如果j处元素优先级更高，即构成了非递增序列，那么i处的元素是可以收进“以j处元素结尾的最长满足条件的stripe”的，那么stripe长度自然就是max(dp[i], dp[j]+1)了。每一轮外循环只修改了i处的dp值，即dp[i]，那么只要将其与max_len取大值即可。
vector<int> dp(stripe.size(), 1);int max_len = 1;for (int i = 0; i < stripe.size(); i++) {
for (int j = 0; j < i; j++) {
if (pri[stripe[j]] >= pri[stripe[i]]) {
dp[i] = max(dp[i], dp[j] + 1);}}max_len = max(max_len, dp[i]);}
感想：本题最重要还是理解题意，“喜欢颜色的顺序”要弄明白。并且要想到dp，关键是dp值表示的意义，这个定义好了其实代码并不复杂。