798236606 发表于 2020-2-27 17:11:40

PTA A_1045 Favorite Color Stripe

本帖最后由 798236606 于 2020-2-27 17:11 编辑

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

解：
动态规划
1.最长不下降子序列（LIS）
#include <cstdio>
#include <cstring>

int n, m, l;
int order;
int list;
int dp;

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 = i;
    }

    scanf("%d", &l);

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

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

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

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

    return 0;
}
2.最长公共子序列（LCS）可重复版
#include <cstdio>
#include <algorithm>

using namespace std;

int n, m, l;
int order;
int list;
int dp;

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 = 0;

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

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

            if (order == list) dp++;
            if (dp > ans) ans = dp;
      }      
    }

    printf("%d", ans);

    return 0;
}
页: [1]
查看完整版本: PTA A_1045 Favorite Color Stripe