1045 Favorite Color Stripe (30point(s)) 需要二刷 *动态规划问题，最长不下降子串问题

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<vector> 
#include<string>
#include<math.h>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#include<stack>
using namespace std;

const int maxn = 210;

bool flag[maxn];
int pro[maxn];
vector<int>num;
vector<int>dp;

int n;
int main() {
    int a,b;
    cin >> n;
    fill(flag, flag + maxn, false);
    cin >> a;
    for (int i = 0; i < a; i++) {
        cin >> b;
        flag[b] = true;
        pro[b] = i + 1;
        //设定优先级，数值越小代表优先级越高；
    }
    cin >> a;
    for (int i = 0; i < a; i++) {
        cin >> b;
        if (flag[b]) {
            num.push_back(pro[b]);
        }
    }
    //进行动态规划；
    dp.resize(num.size());
    //状态转移方程dp[i]=max(dp[i],dp[j]+1);
    //前提：j和i满足要求，且j从1~i-1
    dp[0] = 1;//第一位初始化；
    for (int i = 1; i < dp.size(); i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (num[i] >= num[j]) {
                //如果i得优先级确实大于j得优先级；
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int maxnum = 0;
    for (int i = 0; i < dp.size(); i++) {
        if (dp[i] > maxnum)
            maxnum = dp[i];
    }
    cout << maxnum << endl;
    return 0;
}