hdu 1423 Greatest Common Increasing Subsequence 最大公共上升子序列 DP

发布于:2021-07-24 17:56:33

Greatest Common Increasing Subsequence
Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4590????Accepted Submission(s): 1462






Problem Description


This is a problem from ZOJ 2432.To make it easyer,you just need output the length of the subsequence.


?




Input


Each sequence is described with M - its length (1 <= M <= 500) and M integer numbers Ai (-2^31 <= Ai < 2^31) - the sequence itself.


?




Output


output print L - the length of the greatest common increasing subsequence of both sequences.


?




Sample Input




1

5
1 4 2 5 -12
4
-12 1 2 4



?




Sample Output




2



?


最*一直在做DP题。。现在的进步是,可以看得懂别人的题解了,。


上一个百度文库的文章讲的还是非常不错的。
最长公共上升子序列(LCIS)的*方算法






下面是用O(n^3)的算法。还会更新O(n^2)的算法 。






#include
#include
#define MAX 600

int 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
",ans) ;
if(t != 0)
{
printf("
") ;
}
}

return 0 ;
}






-----------------------------------------------------------------分割线------------------------------------------------------------






晚上更新:


捣鼓了O(n^2)+一维数组的算法,,不得不佩服搞出这个算法的人,神牛啊!!我看都这么费劲,人家却能发明出来。哎,深刻的感受到了这个世界恶意


o(?□?)o


看代码:






#include
#include
#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
",ans) ;
if(t!=0)
{
printf("
") ;
}
}
return 0 ;
}







相关推荐

最新更新

猜你喜欢