目录
1，题目描述
题目大意
输入
输出
说明
2，思路
核心思想
LIS问题
1，问题的定义及复杂之处
2， 动态规划求解问题
3，举例
4，示例代码
3，代码
1，题目描述
Sample Input:
6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6 Sample Output:
7 题目大意
（一开始确实不好理解）
有一个人叫Eva，喜欢特定的颜色按照特定的顺序排列，比如{2，3，1，5，6}，表示颜色2在第一位，颜色3要在2后面，颜色1要在3后面……以此类推（不必所有喜欢的颜色全部出现，刚开始一直在纠结这里）。
这里有一个色带，它的颜色顺序是这样的{2 2 4 1 5 5 6 3 1 1 5 6}，现在需要计算（Eva would like to have the remaining favorite stripe with the maximum length.），按照Eva喜欢的颜色顺序，最长可以拼成多长的色带（原色带的顺序保持不变）。本例中最优解有以下几种：{2 2 1 1 1 5 6}, {2 2 1 5 5 5 6}, {2 2 1 5 5 6 6}, and {2 2 3 1 1 5 6}.
输入
- 第一行： 样例中涉及到的颜色数目N；
- 第二行：Eva喜欢的颜色数目M，M种颜色的编号及顺序；
- 第三行：彩带长度L，依次对应的颜色种类及顺序；
输出
- 满足Eva喜好的颜色及顺序的最大长度；
说明
- Eva可以辨别的颜色数目不超过200；
- 颜色编号1-N；
2，思路
这一题参考了柳神的思路，了解到这其实是一个LIS（Longest Increasing Sequence，最长不下降子序列）的一个变化（Eva喜欢的颜色中，排最前的赋值最小，越往后越大。并将新设定的值替换掉原先色带的颜色编号）。于是乎，转战晴神笔记，了解一下LIS问题。
核心思想
- 重新声明一个数组num，将Eva喜欢的颜色编号，按照先后顺序重新赋值，比如{2 3 1 5 6}，num[2]=1，num[3]=2，num[1]=3……
- 在接受原色带时，剔除Eva不喜欢的颜色，并将喜欢的颜色重新编号：
- 此时问题便转换为LIS问题，并可用动态规划求解。时间复杂度O(n^2);
LIS问题
以下图片内容均来自《算法笔记》——胡凡（又称“晴神笔记”）
1，问题的定义及复杂之处
2， 动态规划求解问题
3，举例
4，示例代码
3，代码
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int main(){
//#ifdef ONLINE_JUDGE
//#else
// freopen("1.txt", "r", stdin);
//#endif
int num[201], data[10000];
int n, m, l; //n涉及到的颜色数 mEva喜欢的颜色数目 l原色带的长度
int id, index = 0;
cin>>n>>m;
for(int i = 1; i <= m; i++){
scanf("%d", &id);
num[id] = i; //为颜色出现的先后顺序编号
}
cin>>l;
for(int i = 0; i < l; i++){
scanf("%d", &id);
if(num[id] > 0){ //只保留Eva喜欢的颜色
data[index++] = num[id];
}
}
int dp[10000], maxLen = 0;
for(int i = 0; i < index; i++){ //原色带处理完之后 长度为index
dp[i] = 1;
for(int j = i - 1; j >= 0; j--){
if(data[i] >= data[j])
dp[i] = max(dp[i], dp[j]+1);//动态方程
}
maxLen = max(maxLen, dp[i]); //记录最大值
}
cout<<maxLen;
return 0;
}