#include <stdio.h>#include <string.h>#define MAX 600int dp[MAX][MAX] ;int max(int a ,int b){return a>b?a:b ;}int main(){int num1[MAX],num2[MAX], t;scanf("%d",&t);while(t–){int n , m ;scanf("%d",&n);for(int i = 1 ; i <= n ; ++i)scanf("%d",&num1[i]);scanf("%d",&m);for(int i = 1 ; i <= m ; ++i)scanf("%d",&num2[i]);memset(dp,0,sizeof(dp)) ;int ans = 0 ;for(int i = 1 ; i <= n ; ++i){for(int j = 1 ; j <= m ; ++j){if(num1[i]!=num2[j])dp[i][j] = dp[i-1][j];if(num1[i] == num2[j]){dp[i][j] = 1 ;for(int k = 1 ; k < j ; ++k){if(num2[j]>num2[k])dp[i][j] = max(dp[i][j],dp[i-1][k]+1) ;}}ans = max(ans,dp[i][j]) ;}}printf("%d\n",ans) ;if(t != 0){printf("\n") ;}}return 0 ;}
—————————————————————–分割线————————————————————
晚上更新：
捣鼓了O(n^2)+一维数组的算法，，不得不佩服搞出这个算法的人，神牛啊！！我看都这么费劲，人家却能发明出来。哎，，深刻的感受到了这个世界恶意
o(╯□╰)o
看代码：
#include <stdio.h>#include <string.h>#define MAX 505 int getMax(int a , int b){return a>b?a:b ;}int main(){int num1[MAX],num2[MAX],dp[MAX],t;scanf("%d",&t);while(t–){int n , m ;scanf("%d",&n);for(int i = 1 ; i <= n ; ++i)scanf("%d",&num1[i]);scanf("%d",&m);for(int i = 1 ; i <= m ; ++i)scanf("%d",&num2[i]);memset(dp,0,sizeof(dp)) ;int ans = 0 ;for(int i = 1 ; i <= n ; ++i){int max = 0 ;for(int j = 1 ; j <= m ; ++j){if(num1[i]>num2[j] && max < dp[j])max = dp[j] ;if(num1[i] == num2[j]){dp[j] = max+1 ;}ans = getMax(ans,dp[j]) ;}}printf("%d\n",ans) ;if(t!=0){printf("\n") ;}}return 0 ;}
便是不再存在着任何我曾经对你有过的希望。
