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

为什么应该是TLE却报WA?

Posted by Rieman at 2010-11-24 13:50:08 on Problem 1934
我测试了官方数据,发现我的程序结果全对,但是超时,为什么它会报WA呢?
#include <iostream>
using namespace std;
const int inf=5000,maxint=(int)1e6;
char sx[81],sy[81],rout[inf][81],tp[81];
int k,d,xlen,ylen,dp[81][81],len;
void search(int i,int j)
{
  int di,dj;
  if(i==xlen||j==ylen)
	return;
  if(sx[i]==sy[j])
  {
	tp[k++]=sx[i];
	if(k==len)
	  tp[k]=0,strcpy(rout[d++],tp);
	search(i+1,j+1);
	k--;
	return;
  }
  di=i;
  while(di<xlen&&sx[di]!=sy[j])
	di++;
  if(di==xlen)
	goto poy;
  tp[k++]=sy[j];
  if(k==len)
	tp[k]=0,strcpy(rout[d++],tp);
  search(di+1,j+1);
  k--;
  poy:
  dj=j;
  while(dj<ylen&&sx[i]!=sy[dj])
	dj++;
  if(dj==ylen)
	goto pox;
  tp[k++]=sx[i];
  if(k==len)
	tp[k]=0,strcpy(rout[d++],tp);
  search(i+1,dj+1);
  k--;
  pox:	search(i+1,j+1);
}
int main()
{
  int i,j;
  cin>>sx>>sy;
  xlen=strlen(sx);
  ylen=strlen(sy);
  for(i=0;i<xlen+1;i++)
	dp[i][0]=0;
  for(i=0;i<ylen+1;i++)
	dp[0][i]=0;
  for(i=1;i<xlen+1;i++)
	for(j=1;j<ylen+1;j++)
	  if(sx[i-1]==sy[j-1])
		dp[i][j]=dp[i-1][j-1]+1;
	  else if(dp[i-1][j]>dp[i][j-1])
		dp[i][j]=dp[i-1][j];
	  else
		dp[i][j]=dp[i][j-1];
  len=dp[xlen][ylen];
  d=k=0;
  search(0,0);
  for(i=0;i<d;i++)
  {
	k=i;
	for(j=i+1;j<d;j++)
	  if(strcmp(rout[k],rout[j])>0)
		k=j;
	strcpy(tp,rout[k]);
	strcpy(rout[k],rout[i]);
	strcpy(rout[i],tp);
  }
  cout<<rout[0]<<endl;
  k=1;
  for(i=1;i<d;i++)
	if(strcmp(rout[i],rout[i-1]))
	  cout<<rout[i]<<endl,k++;
  cout<<k<<endl;
  return 0;
}

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