Favorite Color Stripe (30)

//一开始用dfs结果超时了
//然后发现这很像动态规划问题的最长公共子串问题,只有稍微改改转移方式就行了,难怪才2星难度

 //状态转移根据左边和上边的值来确定,所以下标加1,0行初始化为0.

/*转移矩阵
序      0  1  2  3  4  5  6  7  8  9   10  11  12

    色     2  2  4  1  5  5  6  3   1   1   5   6
    
0       0  0  0  0  0  0  0  0  0   0   0    0  0
  
1   2   0  1  2  2  2  2  2  2  2   2   2   2   2

2   3   0  1  2  2  2  2  2  2  3   3   3   3   3

3   1   0  1  2  2  3  3  3  3  3   4   5   5   5

4   5   0  1  2  2  3  4  5  5  5   5   5   6   6

5   6   0  1  2  2  3  4  6  6  6   6   6   6   7

*/

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int N;
    cin>>N;
    
    int M;
    cin>>M;
    vector<int> order(M);
    for(int i=0;i<M;i++){
        cin>>order[i];
    }
    
    int K;
    cin>>K;
    vector<int> stripe(K);
    for(int i=0;i<K;i++){
        cin>>stripe[i];
        
    }
    
    
    vector<vector<int>> dp(M+1,vector<int>(K+1,0));
    
    for(int i=0;i<M;i++){
        for(int j=0;j<K;j++){
            
            dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            if(order[i]==stripe[j])dp[i+1][j+1]++;
            
        }
    }
    
    cout<<dp.back().back();
    
    return 0;
}

/**
 * 题目：PAT_A-动规-中等-1045-最长有序序列
 *
 * 说明：
 * 1. 输入：颜色种类N; 整数M, 喜爱颜色序列cl_fav[1,M]; 整数L, 原始布条序列cl_stripe[1,L]
 * 2. 任务：喜爱颜色序列定义了颜色的顺序与合法与否，依此，找出最长有序序列（不一定连续）
 * 3. 输出：最长有序序列长度
 *
 * 技巧：
 * 1. 动态规划
 * 2. 动态规划问题转化：
 *    DAG问题
 * 3. 状态量表达（卡壳处）：
 *    d[i] <=> 以cl_stripe[i]结尾（若可以）的喜爱布条的最长长度
 *    所求结果 <=> max(d[i]), 枚举所有i
 * 4. 决策种类：
 *    详细见状态转移方程
 * 5. 状态转移方程：
 *    d[i] = max(d[j] + 1), 枚举j满足<j,i>有向边存在，即喜爱颜色中j在i的左边
 * 6. 程序实现：
 *    终点表，迭代法，填表法
 * 7. 注意！一定要让所有极端、边界情况都得到控制！让各个变量根据其含义在任何情况下都是正确的！
 * 8. 本题的非喜爱颜色其实可以在一开始就剔除出cl_stripe[]
 *
 */
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

#define MAXN        209
#define MAXM        209
#define MAXL        10009

int N;
int M;
int cl_fav[MAXM];           /* favourite colors */
int L;
int cl_stripe[MAXL];        /* colors of the stripe */

int id[MAXN];               /* id[cl_fav[i]] = i */
int d[MAXL];                /* d[i] <=> 以cl_stripe[i]结尾的喜爱布条的最长长度 */

int mxl_fs;                 /* maxlen of favourite stripe */

void init_all(void)
{
    cin >> N;
    cin >> M;
    (void)memset(id, 0, sizeof(id));
    for (int i = 1; i <= M; ++i) {
        cin >> cl_fav[i];
        id[cl_fav[i]] = i;
    }
    cin >> L;
    for (int i = 1; i <= L; ++i) {
        cin >> cl_stripe[i];
    }
}

void solve_d(void)
{
    for (int i = 1; i <= L; ++i) {
        if (id[cl_stripe[i]] <= 0) {
            d[i] = 0;
            continue;
        }
        d[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (id[cl_stripe[j]] <= 0) {
                continue;
            }
            if (id[cl_stripe[i]] >= id[cl_stripe[j]]) {
                d[i] = max(d[i], d[j] + 1);
            }
        }
    }

    mxl_fs = 0;
    for (int i = 1; i <= L; ++i) {
        mxl_fs = max(mxl_fs, d[i]);
    }
}

int main(void)
{
    (void)init_all();
    (void)solve_d();

    cout << mxl_fs;
    return 0;
}

/*喜欢2 1 3 ，那么选中1后面就不能选2了，故序列改成1 2 3，
就是将输入数据按输入顺序改变其权值，转化成最长非递减子序列问题了
动态规划 
dp思路：dp[i] 为0到第i项的最长非递减子序列长度。
dp[i] = max(dp[j])+1    a[j] < a[i]
这样是o（n^2),二分优化后 dp[i]保存的是长度为i时最长递增子序列的最小结尾 复杂度为nlogn。
*/
#include <bits/stdc++.h>
using namespace std;
const int AX = 1e4 + 666 ;
int b[206] ;
int dp[AX] ;
map<int,int>mp;
vector<int>a ;
int main() {
	int n , m , k , x ;
	scanf("%d",&k);
	scanf("%d",&m);
	for( int i = 1 ; i <= m ; i++ ) {
		scanf("%d",&x);
		mp[x] = i;
	}
	scanf("%d",&n);
	for( int i = 0 ; i < n ; i++ ) {
		scanf("%d",&x);
		if(mp[x]) a.push_back(mp[x]);
	}
	dp[0] = a[0] ;
	int tot = 0 ;
	for( int i = 1 ; i < a.size() ; i++ ) {
		if( a[i] >= dp[tot] ) {
			dp[++tot] = a[i] ;
		} else {
			int pos = upper_bound( dp , dp + tot + 1 , a[i] ) - dp ;
			dp[pos] = a[i] ;
		}
	}
	printf("%d",tot+1);
	return 0 ;
}

#include<stdio.h>
int order[204];
int num[10005];
int dp[10005];
int main()
{
	int n;
	while( scanf("%d",&n)!= EOF )
	{
		int x;
		scanf("%d",&x);
		for( int i  = 0 ; i < x ; i++ )
			scanf("%d",&order[i]);
		int y;
		scanf("%d",&y);
		for( int i = 0 ; i < y ; i++ )
		{
			scanf("%d",&num[i]);
			dp[i] = 0;
		}
//按照喜欢颜色的顺序标号
//标号即为选择该位置颜色时最长序列
		for( int i = 0 ; i < x ; i++ )
		{
			int max = 0;
			for( int j = 0 ; j < y ; j++ )
			{
				if( order[i] == num[j] )
				{
					dp[j] = ++max;
				}
				else
				{
					if( dp[j] > max )
					max = dp[j];
				}
			}
		}
//选择最长序列
		int ans = 0;
		for( int i = 0 ; i < y ; i++ )
		{
		 	if( dp[i] > ans )
		 	ans = dp[i];
		 }
		 printf("%d\n",ans);
	}
	return 0;
}

举例子：
eva的喜好 2 3 1 5 6
建立映射表 (2,1) (3,2) (1,3) (5,4) (6,5)

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 203;
const int MAXL = 10003;
int a[MAXN], stripe[MAXL];
int dp[MAXN][MAXL] = {0};

int main()
{     int n,m,l,Max=0;     cin>>n>>m;     for(int i=0;i<m;i++)         cin>>a[i];     cin>>l;     for(int i=0;i<l;i++)         cin>>stripe[i];     for(int i=0;i<m;i++)         for(int j=0;j<l;j++)         {             dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);             if(a[i] == stripe[j])                 dp[i+1][j+1]++;             Max = max(Max, dp[i+1][j+1]);         }     cout<<Max<<endl;     return 0;
}

	

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    // 读入数据
    int N, M, L; cin >> N >> M;
    vector<int> fc(M+1);
    for(int i=1; i<=M; i++) cin >> fc[i];
    cin >> L; vector<int> stripe(L+1);
    for(int i=1; i<=L; i++) cin >> stripe[i];

    // 动态规划处理
    vector<vector<int> > dp(M+1, vector<int>(L+1, 0));
    for(int i=1; i<=M; i++) {
        for(int j=1; j<=L; j++) {
            dp[i][j] = max(dp[i-1][j-1], dp[i][j-1]);
            if(stripe[j] == fc[i]) {
                dp[i][j]++;
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }
    cout << dp[M][L] << endl;
    return 0;
} 

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> P;
typedef long long ll;

const int N = 205;
const int M = 205;
const int L = 10005;

int n, m, l;
int favorite[N];
int original[L];
int dp[L][M];

void debug() {
  for (int i = 1; i <= l; i++) {
    for (int j = 1; j <= m; j++) {
      printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
    }
  }
}

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  cin >> n;
  cin >> m;
  for (int i = 1; i <= m; i++) cin >> favorite[i];
  cin >> l;
  for (int i = 1; i <= l; i++) cin >> original[i];
  for (int i = 1; i <= l; i++) {
    for (int j = 1; j <= m; j++) {
      dp[i][j] = dp[i - 1][j];
      if (original[i] == favorite[j]) {
        for (int k = 1; k <= j; k++) {
          dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1);
        }
      }
    }
  }
  // debug();
  int ans = 0;
  for (int i = 1; i <= m; i++) ans = max(ans, dp[l][i]);
  cout << ans << endl;
  return 0;
}

#include<cstdio>
int n,m,L,color,ans=-1,dp[500],pos[500];
int main(){
	scanf("%d", &n);
	scanf("%d", &m);
	for(int i=1;i<=m;i++){
		scanf("%d", &color);
		pos[color]=i;
	}
	scanf("%d", &L);
	for(int i=0;i<L;i++){
		scanf("%d", &color);
		if(pos[color]!=0){
			int Max=-1,Pos=pos[color];
			for(int j=1;j<=Pos;j++)
				if(dp[j]>=Max)
					Max=dp[j]+1;
			dp[Pos]=Max;
			if(dp[Pos]>ans) ans=dp[Pos];
		}
	}
	printf("%d", ans);
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define color int

int main() {
    int N, M, L;
    cin >> N >> M;
    color n[M];
    map<color, int> find_color;
    for (int m = 0; m < 205; ++m) {
        find_color[m] = -1;
    }
    for (int i = 0; i < M; ++i) {
        cin >> n[i];
        find_color[n[i]] = i;
    }

    cin >> L;
    color l[L];
    for (int j = 0; j < L; ++j)
        cin >> l[j];

    vector<int> longest(M, 0);
    for (int k = 0; k < L; ++k) {
        if(find_color[l[k]] != -1) {
            int max = -1;
            for (int i = 0; i <= find_color[l[k]]; ++i) {
                if(longest[i] > max) {
                    max = longest[i];
                }
            }
            longest[find_color[l[k]]] = max + 1;
        }
    }

    // 以最后一个元素结尾不一定是最长的：cout << *(longest.end() - 1) << endl;
    cout << *max_element(longest.begin(), longest.end()) << endl;

    return 0;
}

//我就是个*****，开始把题目看错了，哪个实例以为favorite color为6，恰好能对应上，然后看她喜欢的颜色居然有重复，把我给整懵了
//然后小技巧，存优先级时将直接将stripes换成对应的优先级，这样就变成求最长不减序列。
//看到有大神说用最长公共序列，设喜欢的颜色顺序为fc数组，彩带颜色为stripe数组。
//把fc竖着排，把stripe横着排

	//dp[i][j]表示以颜色fc[i]和stripe[j]结尾的最大长度



	// dp[i][j] = max(dp[i-1][j], dp[i-1][j])+1   当fc[i]== stripe[j]时



	// dp[i][j] max(dp[i-1][j], dp[i][j-1])      当fc[i]！= stripe[j]时
//dp[i][j-1]表示按照颜色喜好下标从0到i，彩带长度为j-1的时候所能得到的最大长度。
//因此可以直到当彩带长度增加1时,即dp[i][j]一定大于等于dp[i][j-1]。而且当fc[i]==stripes[j]时增加1。
//dp[i-1][j]表示按照颜色喜好下标从0到i-1，彩带长度为j的时候所能得到的最大长度。 //因此可以看出当fc再增加一个的时候，即dp[i][j]也大于等于dp[i-1][j],当fc[i]=stripes[j]时增加1。 

#include<iostream>
(720)#include<vector>
#include<algorithm>
(831)#include<map>
using namespace std;
const int maxn = 201;
int main() {
	int m, n, x;
	cin >> n;
	vector<int>favorite;
	map<int, int>mymap;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		mymap[x] = i;
		favorite.push_back(x);
	}
	int num;
	vector<int>stripes;
	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> x;
		if (mymap[x])//去除掉不喜欢的颜色
			stripes.push_back(mymap[x]);//直接将优先级当做彩带颜色!!!
	}
	vector<int>dp(num);
	dp[0] = 1;
	for (int i = 1; i < stripes.size(); i++) {
		dp[i] = -1;
		bool flag = false;
		for (int j = 0; j < i; j++) {
			if (stripes[i] >= stripes[j]) {//单调不减
				dp[i] = max(dp[i], dp[j] + 1);
				flag = true;
			}
		}
		if (!flag) {
			dp[i] = 1;
		}
	}
	int max = -1;
	for (int i = 0; i < stripes.size(); i++) {
		if (dp[i] > max) {
			max = dp[i];
		}
	}
	printf("%d", max);
}

#include<iostream>
using namespace std;
int n, m,temp,l,seq[200],len[200];
bool has[201];
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> temp;
		has[temp] = true;
		seq[i] = temp;
	}
	cin >> l;
	for (int i = 0; i < l; i++) {
		cin >> temp;
		if (has[temp]) {
			int max = len[0];
			for (int j = 0; j < m; j++) {
				if (len[j] > max) max = len[j];
				if (seq[j] == temp) len[j] = max + 1;
			}
		}
		else {
			l--; i--;
		}
	}
	int max = len[0];
	for (int i = 0; i < m; i++) if (max < len[i]) max = len[i];
	cout << max;
	return 0;
}

#include<iostream>
using namespace std;
int N,M,L,tp,sq[201],pos[201],dp[201],colors[10001];
int main(){
    cin>>N>>M;
    for(int i = 1 ; i <= M ; i++){
        cin >> tp;
        pos[tp] = i;//颜色tp在喜欢的序列中的位置
        sq[i] = tp;//喜欢的第i种颜色是tp
    }
    cin >> L;
    for(int i = 1; i <= L; i++){
        cin>>colors[i];
    }
    for(int i = 1; i <= L; i++){
        int c = colors[i];
        if(pos[c] != 0){//若该颜色在喜欢的序列中
            int subMax = 0;
            for(int j = 1; j <= pos[c]; j++){
                subMax = max(subMax,dp[sq[j]]);//找到前面的最长序列
            }
            dp[c] = subMax + 1;//dp数组表示以下标c结尾的最长序列的长度
        }
    }
    int res = 0;
    for(int i = 1 ;i <= N ;i ++){
        res = max(dp[i],res);//比较得出最大的长度
    }
    cout<<res;
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;
vector<int>ar;
int dep[10000] = { 0 }, pri[210] = { 0 }, n, m, total, tem,maxd=1;

int main()
{     cin >> total >> m;     for (int i = 0; i < m; i++) {         cin >> tem;         pri[tem] = 200 - i;     }     cin >> n;     for (int i = 0; i < n; i++) {         cin >> tem;         if (pri[tem] > 0)ar.push_back(tem);     }     dep[0] = 1;     for (int i = 1; i < ar.size(); i++) {         dep[i] = 1;         for (int j = 0; j < i; j++) {             if (pri[ar[j]] >= pri[ar[i]] && dep[j] + 1 > dep[i]) {                  dep[i] = dep[j] + 1;                  if (dep[i] > maxd)maxd = dep[i];             }         }     }     cout << maxd;

    return 0;
}

	优雅解决  最低空间负责度



	#include <bits/stdc++.h>



	using namespace std;



	inta[202],b[202],c[202];



	intmain()



	{



	    intn,m,l,box,ans=0;



	    scanf("%d %d",&n,&m);



	    memset(b,-1,sizeof(b));



	    for(inti=0;i<m;i++){



	       scanf("%d",&a[i]);



	       b[a[i]]=i;



	    }



	    scanf("%d",&l);



	    for(inti=0;i<l;i++){



	        scanf("%d",&box);



	        intmaxx=0;



	        if(b[box]!=-1){



	            for(intj=0;j<=b[box];j++)maxx=max(c[a[j]],maxx);



	        }



	        c[box]=maxx+1;



	        ans=max(c[box],ans);



	    }



	    printf("%d\n",ans);



	    return0;



	}

N=int(input())
A=list(map(int,input().split()[1:]))
B=list(map(int,input().split()[1:]))
F=[[0]*len(B) for _ in range(len(A)+1)]
for i in range(1,len(A)+1):
    for j in range(len(B)):
        F[i][j]=max(F[i-1][j],F[i][j-1])
        F[i][j]+=1 if A[I-1]==B[j] else 0
print(F[len(A)][len(B)-1])

#include<iostream>
#include<cstdio>
using namespace std;
int love[10010];
//求最长不下降子序列
int color[10010];
int dp[10010];
int main()
{
    freopen("data.in","r",stdin);
    int nn,n;
    cin>>nn>>n;
    for(int i=1;i<=n;i++)
    {
        int t;
        cin>>t;
        love[t]=i;
    }
    int L,num=0;
    cin>>L;
    for(int i=0;i<L;i++)
    {
        int c;
        cin>>c;
        if(love[c]>0)
          color[num++]=love[c];
    }
    for(int i=0;i<num;i++)
    {
        dp[i]=1;
        for(int j=0;j<i;j++)
        {
            if(color[j]<=color[i]  && dp[i]<dp[j]+1)
                dp[i]=dp[j]+1;
        }
    }
    int k=0;
    for(int i=0;i<num;i++)
    {
        if(dp[k]<dp[i])
            k=i;
    }
    cout<<dp[k];
   return 0;
}