關于子序列什么什么的問題，以前一直沒怎么在意過，直到省賽突然考了一個赤裸裸的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)

?

View Code

#include<iostream>
#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<n;i++){k=0;for(j=0;j<m;j++){if(a[i]==b[j]) //如果a[i]==b[j]
            {if(f[j]<f[k]+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<m;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<n;i++){scanf("%d",&a[i]);}scanf("%d",&m);for(j=0;j<m;j++){scanf("%d",&b[j]);}printf("%d\n",LCIS());if(t)printf("\n");}return 0;
}

具體練習可以做做HDU 1423和湖南省第八屆程序設計大賽的J題

?

轉載于:https://www.cnblogs.com/ka200812/archive/2012/10/15/2723870.html

總結

以上是生活随笔為你收集整理的最长公共上升子序列 LCIS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。