PTA A_1045 Favorite Color Stripe

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805437411475456

解：
动态规划
1.最长不下降子序列（LIS）

#include <cstdio>
#include <cstring>

int n, m, l;
int order[205];
int list[10010];
int dp[10010];

int main(void)
{
    freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &m);

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

    for (int i = 0; i < m; i++)
    {
        int a;

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

    scanf("%d", &l);

    int num = 0;
    while (l--)
    {
        int a;

        scanf("%d", &a);
        if (order[a] != -1) list[num++] = order[a];
    }

    int ans = -1;   
    for (int i = 0; i < num; i++)
    {
        dp[i] = 1;

        for (int j = 0; j < i; j++)
            if (list[j] <= list[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
        
        if (dp[i] > ans) ans = dp[i];
    }
        
    printf("%d", ans);

    return 0;
}

2.最长公共子序列（LCS）可重复版

#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, l;
int order[205];
int list[10010];
int dp[205][10010];

int main(void)
{
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d", order + i);
 
    scanf("%d", &l);
    for (int i = 1; i <= l; i++)
        scanf("%d", list + i);    

    // for (int i = 1; i <= m; i++)
    //     dp[i][0] = 0;

    // for (int i = 1; i <= l; i++)
    //     dp[0][i] = 0;

    int ans = -1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= l; j++)
        {
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

            if (order[i] == list[j]) dp[i][j]++;
            if (dp[i][j] > ans) ans = dp[i][j];
        }        
    }

    printf("%d", ans);

    return 0;
}