Time
Limit: 3000/1000 MS (Java/Others) Memory Limit:
65535/32768 K (Java/Others)
Total Submission(s):
1894 Accepted Submission(s):
568
start length_a , length_b,lcs[legth_a][length_b]; for ： i from 1 to length_a ; for : j from 1 to legth_b ; if a[i] == b[j] lcs[i][j] = lcs[i][j]+1; else if a[i]!=b[j] lcs[i][j] = max { lcs[i][j-1] , lcs[i-1][j]} ; end for ; end for ; return lcs[length_a][length_b] ; end
c++实现代码：
1 int Lcs(int aa[] ,int bb[] ,int la ,int lb) 2 { 3 int cc[la][lb]; 4 menset(cc,0,sizeof(cc)); 5 for(i=1;i<=la ; i++) 6 { 7 for(j=1 ; j<=lb ;j++) 8 { 9 if(aa[i]==bb[j]) 10 cc[i][j]=cc[i-1][j-1]+1; 11 if(aa[i]!=bb[j]) 12 { 13 cc[i][j]= cc[i][j-1]>cc[i-1][j]? cc[i][j-1]:cc[i-1][j]; 14 } 15 } 16 } 17 return cc[la][lb]; 18 }
对于对递增函数：
就如同这道题：
看看这道题的代码：
1 //lcis algorithm 2 #include<stdio.h> 3 #include<string.h> 4 #define maxn 205 5 int aa[maxn]; 6 int lcs[maxn]; 7 int main() 8 { 9 int test,n,i,j,maxc,w,res; 10 scanf("%d",&test); 11 while(test--) 12 { 13 scanf("%d",&n); 14 for(i=1;i<=n;i++) 15 scanf("%d",aa+i); 16 res=0; 17 memset(lcs,0,sizeof(lcs)); 18 for(i=1;i<=n;i++) 19 { 20 maxc=0; 21 for( j=n;j>=i;j--) //每一次重边一次 22 { 23 if(aa[i]==aa[j]&&lcs[j]<maxc+1) 24 lcs[j]=maxc+1; 25 else 26 if(aa[i]>aa[j]&&maxc<lcs[j]) 27 maxc=lcs[j]; 28 //如何判断是否为重边 29 if(i<j) 30 { 31 if(res<2*lcs[j]) 32 res=2*lcs[j]; 33 } 34 else //重边 35 { 36 if(res<2*lcs[j]-1) 37 res=2*lcs[j]-1; 38 } 39 } 40 } 41 printf("%d\n",res); 42 } 43 return 0; 44 }
HDUOJ-----4512吉哥系列故事——完美队形I（LCIS）,布布扣,bubuko.com
HDUOJ-----4512吉哥系列故事——完美队形I（LCIS）
原文：http://www.cnblogs.com/gongxijun/p/3632322.html