| ||||||||||
| 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