输出一条 LCIS
1 #include "bits/stdc++.h" 2 using namespace std; 3 int T; 4 int len1, len2; 5 int s1[510], s2[510]; 6 int dp[510][510]; 7 int choice[510][510]; 8 9 10 int main() 11 { 12 scanf("%d", &T); 13 while(T--) { 14 memset(dp, 0, sizeof(dp)); 15 memset(choice, 0, sizeof(choice)); 16 scanf("%d", &len1); 17 int i, j; 18 for(i = 1; i <= len1; ++i) { 19 scanf("%d", &s1[i]); 20 } 21 scanf("%d", &len2); 22 for(j = 1; j <= len2; ++j) { 23 scanf("%d", &s2[j]); 24 } 25 26 for(i = 1; i <= len1; ++i) { 27 int k = 0; 28 for(j = 1; j <= len2; ++j) { 29 if(s1[i] == s2[j]) { 30 dp[i][j] = dp[i - 1][k] + 1; 31 choice[i][j] = 1000 * (i - 1) + k; 32 } 33 else { 34 dp[i][j] = dp[i - 1][j]; 35 choice[i][j] = choice[i - 1][j]; 36 if(s1[i] > s2[j] && dp[i - 1][k] < dp[i - 1][j]) { 37 k = j; 38 } 39 } 40 // printf("dp[%d][%d] == %d ", i ,j, dp[i][j]); 41 } 42 } 43 44 int end_pos; 45 int res = 0; 46 for(j = 1; j <= len2; ++j) { 47 if(res < dp[len1][j]) { 48 res = dp[len1][j]; 49 end_pos = j; 50 } 51 } 52 printf("%d ", res); 53 if(res == 0) { 54 continue; 55 } 56 int state_1, state_2, tmp; 57 state_1 = len1; 58 state_2 = end_pos; 59 int tot_ans = 0; 60 while(state_2) { 61 ++tot_ans; 62 s1[tot_ans] = s2[state_2]; 63 tmp = choice[state_1][state_2]; 64 state_1 = tmp / 1000; 65 state_2 = tmp % 1000; 66 } 67 while(tot_ans) { 68 printf("%d ", s1[tot_ans]); 69 --tot_ans; 70 } 71 printf(" "); 72 } 73 } 74 //2 75 //5 76 //1 4 2 5 -12 77 //4 78 //-12 1 2 4 79 80 81 //2 82 //5 83 //1 2 3 4 5 84 //1 85 //9