| ||||||||||
| 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