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
5
1 4 2 5 -12
4
-12 1 2 4
Sample Output
2
题意：求最长公共上升子序列。
做法：设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");
}
}