最长公共上升子序列 LCIS

　　关于子序列什么什么的问题，以前一直没怎么在意过，直到省赛突然考了一个赤裸裸的LCIS，这下才着急了，因为忘记怎么做了，而且模版也没有带。从第三名一直掉到第11名，而且超上来的，全都是会做这题的o(╯□╰)o。  虽然最后还是保住了一个一等奖，不过真是太不甘心了。

 

　　这里总结一个O(nm)的算法。

　　设题目给出a[],b[]两个序列。f[j]表示b序列到j的时候，与a[？？]序列构成最长公共上升子序列的最优解。其中a[？？]序列，从1到n枚举过来。

　　如果某一个时刻a[i]==b[j]，那么显然，我们就应该在0到j-1中，找一个f值最大的来更新最优解。这和求上升子序列是思想是一样的。另外，在枚举b[j]的时候，我们顺便保存一下小于a[i]的f值最大的b[j]，这样在更新的时候，我们就可以做到O(1)的复杂度，从而将整个算法的复杂度保证在O(nm)

 

#include
#include<string>
using namespace std;int max(int a,int b)
{return a>b?a:b;
}int a[1010],b[1010];
int f[1010],n,m;int LCIS()
{int i,j,k;memset(f,0,sizeof(f));for(i=0;i){k=0;for(j=0;j){if(a[i]==b[j]) //如果a[i]==b[j]
            {if(f[j]1) //就在0到j-1之间，找一个b[k]小于a[i]的f[k]值最大的解f[j]=f[k]+1;}if(a[i]>b[j]) //0到j-1中，对于小于a[i]的，保存f值的最优解
            {if(f[k]<f[j])k=j;}}}int ans=0;for(i=0;i)ans=max(ans,f[i]);return ans;
}int main()
{int t,i,j;freopen("D:\in.txt","r",stdin);scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i){scanf("%d",&a[i]);}scanf("%d",&m);for(j=0;j){scanf("%d",&b[j]);}printf("%d
",LCIS());if(t)printf("
");}return 0;
}

具体练习可以做做HDU 1423和湖南省第八届程序设计大赛的J题