PTA A_1045 Favorite Color Stripe

798236606

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

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

1. #include <cstdio>
   
2. #include <cstring>
   
3. 
   
4. int n, m, l;
   
5. int order[205];
   
6. int list[10010];
   
7. int dp[10010];
   
8. 
   
9. int main(void)
   
10. {
    
11.     freopen("input.txt", "r", stdin);
    
12.     scanf("%d %d", &n, &m);
    
13. 
    
14.     memset(order, -1, sizeof(order));
    
15. 
    
16.     for (int i = 0; i < m; i++)
    
17.     {
    
18.         int a;
    
19. 
    
20.         scanf("%d", &a);
    
21.         order[a] = i;
    
22.     }
    
23. 
    
24.     scanf("%d", &l);
    
25. 
    
26.     int num = 0;
    
27.     while (l--)
    
28.     {
    
29.         int a;
    
30. 
    
31.         scanf("%d", &a);
    
32.         if (order[a] != -1) list[num++] = order[a];
    
33.     }
    
34. 
    
35.     int ans = -1;   
    
36.     for (int i = 0; i < num; i++)
    
37.     {
    
38.         dp[i] = 1;
    
39. 
    
40.         for (int j = 0; j < i; j++)
    
41.             if (list[j] <= list[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
    
42.         
    
43.         if (dp[i] > ans) ans = dp[i];
    
44.     }
    
45.         
    
46.     printf("%d", ans);
    
47. 
    
48.     return 0;
    
49. }

复制代码

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

1. #include <cstdio>
   
2. #include <algorithm>
   
3. 
   
4. using namespace std;
   
5. 
   
6. int n, m, l;
   
7. int order[205];
   
8. int list[10010];
   
9. int dp[205][10010];
   
10. 
    
11. int main(void)
    
12. {
    
13.     // freopen("input.txt", "r", stdin);
    
14.     scanf("%d %d", &n, &m);
    
15.     for (int i = 1; i <= m; i++)
    
16.         scanf("%d", order + i);
    
17. 
    
18.     scanf("%d", &l);
    
19.     for (int i = 1; i <= l; i++)
    
20.         scanf("%d", list + i);   
    
21. 
    
22.     // for (int i = 1; i <= m; i++)
    
23.     //     dp[i][0] = 0;
    
24. 
    
25.     // for (int i = 1; i <= l; i++)
    
26.     //     dp[0][i] = 0;
    
27. 
    
28.     int ans = -1;
    
29.     for (int i = 1; i <= m; i++)
    
30.     {
    
31.         for (int j = 1; j <= l; j++)
    
32.         {
    
33.             dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
    
34. 
    
35.             if (order[i] == list[j]) dp[i][j]++;
    
36.             if (dp[i][j] > ans) ans = dp[i][j];
    
37.         }        
    
38.     }
    
39. 
    
40.     printf("%d", ans);
    
41. 
    
42.     return 0;
    
43. }

复制代码