Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我怎么感觉自己的算法是O(n^2)的啊,但wa

Posted by kevin655 at 2006-07-13 12:09:34 on Problem 2127
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator