【记忆化搜索】bzoj1055 [HAOI2008]玩具取名

f(l,r,c)表示sl...sr能否被合成字符c。

#include<cstdio>
#include<cstring>
using namespace std;
int m[95],n;
int mem[201][201][95];
char s[201],To[95][17][3];
bool equal(char a[],int la,int ra,char b[],int lb,int rb)
{
for(int i=la,j=lb;i<=ra;++i,++j)
if(a[i]!=b[j])
return 0;
return 1;
}
bool f(int l,int r,char c)
{
if(mem[l][r][c]!=-1) return mem[l][r][c];
if(l==r) return (s[l]==c?(mem[l][r][c]=1):(mem[l][r][c]=0));
if(r-l+1==2)
{
for(int i=1;i<=m[c];++i)
if(equal(s,l,r,To[c][i],0,1))
return mem[l][r][c]=1;
return mem[l][r][c]=0;
}
for(int i=l;i<r;++i)
for(int j=1;j<=m[c];++j)
if(f(l,i,To[c][j][0])&&f(i+1,r,To[c][j][1]))
return mem[l][r][c]=1;
return mem[l][r][c]=0;
}
int main()
{
scanf("%d%d%d%d",&m['W'],&m['I'],&m['N'],&m['G']);
for(int i=1;i<=m['W'];++i) scanf("%s",To['W'][i]);
for(int i=1;i<=m['I'];++i) scanf("%s",To['I'][i]);
for(int i=1;i<=m['N'];++i) scanf("%s",To['N'][i]);
for(int i=1;i<=m['G'];++i) scanf("%s",To['G'][i]);
scanf("%s",s); n=strlen(s);
memset(mem,-1,sizeof(mem));
bool flag=0;
if(f(0,n-1,'W')) putchar('W'),flag=1;
if(f(0,n-1,'I')) putchar('I'),flag=1;
if(f(0,n-1,'N')) putchar('N'),flag=1;
if(f(0,n-1,'G')) putchar('G'),flag=1;
if(!flag) printf("The name is wrong!");
puts("");
return 0;
}
上一篇:BZOJ 1055 HAOI2008 玩具取名 动态规划


下一篇:formData上传图片