Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我怎么感觉自己的算法是O(n^2)的啊,但waIn Reply To:Re:这个dp过程对不对?我加了discus说的优化,结果TlE->WA Posted by:navyakula at 2006-02-15 20:36:43 #include "iostream" using namespace std; int lcs(int a[],int b[],int c[],int n,int m) { int i,j,k,len; int **L;//L--存储公共串长度 int **s;//s--存储标号 int **p;//p--记录公共串长为L[i][j]时的,公共串最后一个元素p[i][j]; freopen("2127.in", "r", stdin); L=new int*[n+1]; //初始化 for(i=0;i<=n;i++) L[i]=new int[m+1]; s=new int*[n+1]; //初始化 for(i=0;i<=n;i++) s[i]=new int[m+1]; p=new int*[n+1]; //初始化 for(i=0;i<=n;i++) p[i]=new int[m+1]; for(i=0;i<=n;i++) L[i][0]=0; //初值 for(i=0;i<=m;i++) L[0][i]=0; for(i=0;i<=n;i++) p[i][0]=0; for(i=0;i<=m;i++) p[0][i]=0; for(i=1;i<=n;i++) //计算长度及状态字 for(j=1;j<=m;j++) { if (a[i]==b[j]&&a[i]>p[i-1][j-1]) { //注意,数组a,b都是 从1开始存的 L[i][j]=L[i-1][j-1]+1; p[i][j]=a[i]; s[i][j]=1; //s标号为1,表示a[i]==b[j] } else if (L[i-1][j]>L[i][j-1]) { L[i][j]=L[i-1][j]; p[i][j]=p[i-1][j]; s[i][j]=2; } else { L[i][j]=L[i][j-1]; p[i][j]=p[i][j-1]; s[i][j]=3; } } i=n;j=m; k=len=L[i][j]; //搜索最长公共子序列元素 while (i&&j) { switch(s[i][j]) { case 1: c[k--]=p[i--][j--]; break; case 2: i--; break; case 3: j--; break; default: break; } } return len; } void main() { int i,j,n,m,len,d1[502],d2[502],d3[502]; cin>>n; for(i=1;i<=n;i++) cin>>d1[i]; cin>>m; for(i=1;i<=m;i++) cin>>d2[i]; len=lcs(d1,d2,d3,n,m); cout<<len<<endl; for(j=1;j<=len;j++) cout<<d3[j]<<' '; cout<<endl; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator