1045 Favorite Color Stripe (30分) 最长不上升子序列(DP)

题目

https://pintia.cn/problem-sets/994805342720868352/problems/994805437411475456

题意

给予子序列(指示数的先后关系)和目标序列
求最长不上升子序列(每个数的先后顺序和子序列中的一致)的长度

Sample Input:

6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6

Sample Output:

思路

DFS暴力法只能拿24分(超时)
动态规划：

除掉目标序列中不合法的数
状态转移：if(i在j的后面) dp[i]=max(dp[i],dp[j]+1)

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
int M;
int a[206];//给定子序列
int h[206];//子序列harsh，方便确定数的先后关系
int L;
int b[10006];//目标序列
int c[10006];//除杂后的目标序列
int dp[10006];//状态转移，目标序列c前i个数最大匹配长度

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i) {
        scanf("%d",&a[i]);
        h[a[i]]=i;
    }
    scanf("%d",&L);
    int p=0;
    for(int i=1;i<=L;++i) {
        scanf("%d",&b[i]);
        if(h[b[i]]!=0) c[++p]=b[i];//除杂
    }
    for(int i=1;i<=L;++i)
    {
        dp[i]=1;
        for(int j=1;j<i;++j)
        {
            if(h[c[i]]>=h[c[j]])//i能接到j后面
                dp[i]=max(dp[i],dp[j]+1);
           /**
           a:23156
        
           c:22155631156
              j    i    //此情形下i能接到j后面(3在2后面，顺序正确)
           c:22155631156
               j   i    //此情形下i不能接到j后面(3在1前面，顺序不对)
           **/
        }
    }
    printf("%d
",dp[p]);
    return 0;
}