PAT-1045 Favorite Color Stripe (30 分)

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805437411475456

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

题解：可以把题目转换为，最长不下降序列问题，但是目前还有两个样例过不了，超时 bug ing ,C++就过来，哎，这道题还可以转换为最长公共子序列问题

 1 #include <stdio.h>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 const int maxc=210;
 7 const int maxn=10010;
 8 int A[maxc],B[maxn], dp[maxc][maxn];
 9 
10 int main(){
11     int n,m;
12     scanf("%d%d",&n,&m);
13     for(int i=1; i<=m;i++){
14         scanf("%d",&A[i]);
15     }
16     int L;
17     scanf("%d",&L);
18     for(int i=1;i<=L;i++){
19         scanf("%d",&B[i]);
20     }
21     for(int i=0;i<=m;i++){
22         dp[i][0]=0;
23     }
24     for(int j=0;j<=L;j++){
25         dp[0][j]=0;
26     }
27     for(int i=1;i<=m;i++){
28         for(int j=1;j<=L;j++){
29             int maxx=max(dp[i][j-1],dp[i-1][j]);
30             if(A[i]==B[j]){
31                 dp[i][j]=maxx+1;
32             }else{
33                 dp[i][j]=maxx;
34             }
35         }
36     }
37     printf("%d
", dp[m][L]);
38     return 0;
39 }

 1 '''
 2 15 2 2 4 1 2 2 2 5 5 6 3 1 1 5 6
 3 9
 4 '''
 5 if __name__=="__main__":
 6     hashmap=[-1]*205
 7     n=input().split()
 8     m1=list(map(int,input().split()))
 9     m=m1.pop(0)
10     for i in range(m):
11         hashmap[m1[i]]=i
12     L1=list(map(int,input().split()))
13     L=L1.pop(0)
14     A,dp,preIndex=[-1]*(L),[-1]*(L),[-1]*(L)
15     num=0
16     for i in range(L):
17         if hashmap[L1[i]]>=0:
18             A[num]=hashmap[L1[i]]
19             num+=1
20             
21     dp[0]=1
22     for i in range(1,num):
23         maxL,maxI=0,-1
24         for k in range(i-1,-1,-1):
25             if A[k]>A[i]: continue
26             if dp[k] > maxL:
27                 maxL=dp[k]
28                 maxI=k
29         dp[i]=maxL+1
30         preIndex[i]=maxI
31         
32     maxL,maxI=dp[0],-1
33     for i in range(1,num):
34         if dp[i]>maxL: maxL,maxI=dp[i],i
35 
36     print(maxL)
37     print(A[maxI],end=' ')
38     maxI=preIndex[maxI]
39     while preIndex[maxI]!=-1:
40         print(A[maxI],end=' ')
41         maxI=preIndex[maxI]
42     print(A[maxI])
43

View Code