题解【洛谷P4290】 [HAOI2008]玩具取名

这道题很明显是区间DP。

为了方便表示，我们可以将‘W’、‘I’、‘N’、‘G’分别设为1、2、3、4。

另外，DP可能有点丑，记忆化搜索可能写起来更容易理解。

AC代码：

#include <bits/stdc++.h>

using namespace std;//使用标准名字空间

inline int read()//快速读入

{

	int f=1,x=0;

	char c=getchar();

	while(c<'0' || c>'9')

	{

		if(c=='-')f=-1;

		c=getchar();

	}

	while(c>='0' && c<='9')

	{

		x=x*10+c-'0';

		c=getchar();

	}

	return f*x;

}

string s;

int b[5][5][5],dp[210][210][5],p[130],d[5],len,fl;//定义变量

int main()

{

	p['W']=1,p['I']=2,p['N']=3,p['G']=4;//将字母表示成数字

	for(register int i=1; i<=4; i++)//输入

	{

		d[i]=read();

	}

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

	{

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

		{

			cin>>s;//输入每个字母可以代表的子字符串

			b[p[s[0]]][p[s[1]]][i]=1;//标记这个字符串由i演变而来

		}

	}

	cin>>s;//输入玩具名称

	len=s.size();//记录名称长度

	for(register int i=0; i<len; i++)

	{

		dp[i][i][p[s[i]]]=1;//标记第i个位置

	}

	//开始DP主过程

	for(register int i=len-1; i>=0; i--)

	{

		for(register int j=i+1; j<len; j++)//枚举区间（i，j）

		{

			for(register int k=1; k<5; k++)//枚举字母

			{

				for(register int l=1; l<5 && dp[i][j][k]==0; l++)//如果（i，j）不含有字母k，就枚举字母l

				{

					for(register int o=1; o<5 && dp[i][j][k]==0; o++)//同理

					{

						if(b[l][o][k]==0)//如果字母组合（l，o）不能由字母k演变来

						{

							continue;//就继续循环

						}

						for(register int w=i; w<j && dp[i][j][k]==0; w++)

						{

							dp[i][j][k]|=(dp[i][w][l] & dp[w+1][j][o]);//主要DP步骤，要仔细体会

						}

					}

				}

			}

		}

	}

	//输出

	if(dp[0][len-1][1])

	{

		cout<<'W';

		fl=1;

	}

	if(dp[0][len-1][2])

	{

		cout<<'I';

		fl=1;

	}

	if(dp[0][len-1][3])

	{

		cout<<'N';

		fl=1;

	}

	if(dp[0][len-1][4])

	{

		cout<<'G';

		fl=1;

	}

	//无解输出

	if(fl==0)

	{

		cout<<"The name is wrong!";

	}

	return 0;//完美结束

}

巴特西

题解【洛谷P4290】 [HAOI2008]玩具取名

最新文章

热门文章

巴特西

题解 【洛谷P4290】 [HAOI2008]玩具取名

最新文章

热门文章

题解【洛谷P4290】 [HAOI2008]玩具取名