//GCIS
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "algorithm" 5 using namespace std; 6 int dp[510], Max; 7 int s1[510], s2[510]; 8 int len1, len2; 9 10 int main() 11 { 12 int T, i, j; 13 scanf("%d", &T); 14 while(T--) { 15 scanf("%d", &len1); 16 for(i = 1; i <= len1; ++i) 17 scanf("%d", &s1[i]); 18 scanf("%d", &len2); 19 for(i = 1; i <= len2; ++i) 20 scanf("%d", &s2[i]); 21 memset(dp, 0, sizeof(dp)); 22 for(i = 1; i <= len1; ++i) { 23 Max = 0; 24 for(j = 1; j <= len2; ++j) { 25 if(s1[i] > s2[j]) 26 Max = max(Max, dp[j]); 27 else if(s1[i] == s2[j]) 28 dp[j] = max(dp[j], Max + 1); 29 } 30 } 31 int res = 0; 32 for(i = 1; i <= len2; ++i) { 33 res = max(res, dp[i]); 34 } 35 printf("%d ", res); 36 if(T) 37 printf(" "); 38 } 39 }
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 8 int main() 9 { 10 scanf("%d", &T); 11 while(T--) { 12 memset(dp, 0, sizeof(dp)); 13 scanf("%d", &len1); 14 int i, j; 15 for(i = 1; i <= len1; ++i) { 16 scanf("%d", &s1[i]); 17 } 18 scanf("%d", &len2); 19 for(j = 1; j <= len2; ++j) { 20 scanf("%d", &s2[j]); 21 } 22 23 for(i = 1; i <= len1; ++i) { 24 int k = 0; 25 for(j = 1; j <= len2; ++j) { 26 if(s1[i] == s2[j]) { 27 dp[i][j] = dp[i - 1][k] + 1; 28 } 29 else { 30 dp[i][j] = dp[i - 1][j]; 31 if(s1[i] > s2[j] && dp[i - 1][k] < dp[i - 1][j]) { 32 k = j; 33 } 34 } 35 // printf("dp[%d][%d] == %d ", i ,j, dp[i][j]); 36 } 37 } 38 39 int res = 0; 40 for(j = 1; j <= len2; ++j) { 41 res = max(res, dp[len1][j]); 42 } 43 printf("%d ", res); 44 if(T) { 45 printf(" "); 46 } 47 } 48 } 49 //2 50 //5 51 //1 4 2 5 -12 52 //4 53 //-12 1 2 4