bzoj 1055: [HAOI2008]玩具取名【区间dp】

不难想，就是处理起来比较麻烦

设f[i][j][k]为是否可以把区间(i,j)合并为k，初始状态是f[i][j][s[i]]=1，转移的话另一段枚举长度x，向(i-x,j),(i,j+x)转移

把四个字符hash成1234比较好写（大概

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=205;

int n,c[10],mp[N];

bool f[N][N][10],fl,a[10][10][10];

char ch[5],s[N],rl[10];

int main()

{

	mp['W']=1,mp['I']=2,mp['N']=3,mp['G']=4;

	rl[1]='W',rl[2]='I',rl[3]='N',rl[4]='G';

	scanf("%d%d%d%d",&c[1],&c[2],&c[3],&c[4]);

	for(int i=1;i<=4;i++)

		for(int j=1;j<=c[i];j++)

		{

			scanf("%s",ch+1);

			a[mp[ch[1]]][mp[ch[2]]][i]=1;

		}

	scanf("%s",s+1);

	n=strlen(s+1);

	for(int i=1;i<=n;i++)

		s[i]=mp[s[i]],f[i][i][s[i]]=1;

	for(int l=1;l<n;l++)

		for(int i=1;i+l-1<=n;i++)

		{

			int j=i+l-1;

			for(int k=1;k<=4;k++)

				if(f[i][j][k])

				{

					for(int x=1;x<=l&&j+x<=n;x++)

						for(int y=1;y<=4;y++)

							if(f[j+1][j+x][y])

								for(int z=1;z<=4;z++)

									if(a[k][y][z])

										f[i][j+x][z]=1;

					for(int x=1;x<=l&&i-x>=1;x++)

						for(int y=1;y<=4;y++)

							if(f[i-x][i-1][y])

								for(int z=1;z<=4;z++)

									if(a[y][k][z])

										f[i-x][j][z]=1;

				}

		}

	for(int i=1;i<=4;i++)

		if(f[1][n][i])

			printf("%c",rl[i]),fl=1;

	if(!fl)

		puts("The name is wrong!");

	return 0;

}

巴特西

bzoj 1055: [HAOI2008]玩具取名【区间dp】

最新文章

热门文章