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 |
这回又WA掉了...话说gamy那个TLE...所以用下面的方法剪枝,但还是wa#include <iostream> using namespace std; char s[403],s1[201],s2[201]; bool f[201][201]; int main() { int n = 1,T; cin>>T; while(n <= T) { cin>>s1>>s2>>s; int a[125],i = 0; memset(a,0,sizeof(a)); while(i <= strlen(s1))a[s1[i++]]++; i = 0; while(i <= strlen(s2))a[s2[i++]]++; i = 0; while(i <= strlen(s)) { a[s[i]]--; if (a[s[i]] < 0) { cout<<"Data set "<<n<<": no\n"; return 0; } i++; }//剪枝 memset(f,0,sizeof(f)); i=1; while(s1[i - 1]==s[i - 1]&&i<=(int)strlen(s1))f[i++][0]=1; i=1; while(s2[i - 1]==s[i - 1]&&i<=(int)strlen(s1))f[0][i++]=1; for (i = 1; i <= (int)strlen(s1); i++) { for (int j = 1; j <= (int)strlen(s2); j++) f[i][j] = ((f[i - 1][j] && s1[i - 1] == s[i + j -1])|| (f[i][j - 1] && s2[j - 1] == s[i + j - 1])); } cout<<"Data set "<<n<<": "; if (f[(int)strlen(s1)][(int)strlen(s2)]) cout<<"yes\n"; else cout<<"no\n"; n++; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator