| ||||||||||
| 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 | |||||||||
为什么应该是TLE却报WA?我测试了官方数据,发现我的程序结果全对,但是超时,为什么它会报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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator