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

这道题很明显是区间DP。

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

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

AC代码：

#include 

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=0; i--)
	{
		for(register int j=i+1; j