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