Greatest Common Increasing Subsequenc

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 4 2 5 -12

-12 1 2 4

Sample Output

题意：求最长公共上升子序列。

做法：设f[i][j]表示以b[j]结尾的最长公共上升子序列长度。那么有f[i][j]=f[i-1][j],f[i][j]=max(f[i-1][k]){a[i]=b[j],a[i]>b[k]}

这样直接枚举需要三重，虽然对于本题似乎并不会超时(我不知道有几组数据。。)？但我们可以寻求更好的做法。

可以想到，在一重循环i中，a[i]>b[k]中的a[i]是固定的，也就是说，对于循环k，每次长度都只加1，实际上我们可以用一个变量来维护当前

的j是否满足决策条件 val=max(val,f[i-1][j])(a[i]>b[j]),这样就直接降了一维复杂度。

PS：本题输出格式坑（每个输出间空两行）。

 #include <cstdio>

 #include <iostream>

 #define N 607

 #include <cstring>

 using namespace std;

 int n,m,T,ans;

 int f[N][N],a[N],b[N];

 inline int max(int a,int b) {return a>b?a:b;}

 void Init(){

     scanf("%d",&n);

     for (int i=;i<=n;i++)    scanf("%d",&a[i]);

     scanf("%d",&m);

     for (int i=;i<=m;i++)    scanf("%d",&b[i]);

 }

 void Dp(){

     memset(f,,sizeof(f));

     for (int i=;i<=n;i++){

         int val=;

         if (b[]<a[i]) val=f[i-][];

         for (int j=;j<=m;j++){

             if (a[i]==b[j])    f[i][j]=val+;

             else f[i][j]=f[i-][j];

             if (a[i]>b[j]) val=max(val,f[i-][j]);

         }

     }

     ans=;

     for (int i=;i<=n;i++)    ans=max(f[n][i],ans);

 }

 int main(){

     scanf("%d",&T);

     for(;T--;){

         Init();

         Dp();

         printf("%d\n",ans);

         if (T) printf("\n");

     }

 }

秒客网

HDU 1423 Greatest Common Increasing Subsequence（LCIS）

Greatest Common Increasing Subsequenc

相关文章