区间DP【p4290】[HAOI2008]玩具取名

Description

某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。

现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。

Input

第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。

接下来W行，每行两个字母,表示W可以用这两个字母替代。

接下来I行，每行两个字母,表示I可以用这两个字母替代。

接下来N行，每行两个字母,表示N可以用这两个字母替代。

接下来G行，每行两个字母,表示G可以用这两个字母替代。

最后一行一个长度不超过Len的字符串。表示这个玩具的名字。

Output

一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出）

如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”

这题切了emmm

区间dp

好题.

就是卡我智商。感觉复杂度不太对,但是过了emmm。

我们设\(ok[i][0]\)代表第\(i\)个变化方式的原字符.

且\(ok[i][0]\)只会是\('W'\ 'I'\ 'N'\ 'G'\)

\(ok[i][1]\)存储变化后的第一个字符,\(ok[i][2]\)存储变化后的第二个字符.

然后设\(f[i][j][k]\)代表\(i\)到\(j\)这一段区间能否变成\(k\)这个字符.

表示刚开始读错题了

输出可能变成的即可.

然后判断无解的话,就是判断前面是否有过输出.

区间DP的一般套路.

代码

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define R register

using namespace std;

inline void in(int &x)

{

    int f=1;x=0;char s=getchar();

    while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

    while(isdigit(s)){x=x*10+s-'0';s=getchar();}

    x*=f;

}

int W,I,N,G,tot;

char s[10],str[208];

int ok[208][3];

bool f[208][208][5],flg;

inline int rep(char s)

{

	if(s=='W')return 1;

	if(s=='I')return 2;

	if(s=='N')return 3;

	if(s=='G')return 4;

}

int main()

{

	in(W),in(I),in(N),in(G);

	for(R int i=1;i<=W;i++)

	{

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

		ok[++tot][0]=1;

		ok[tot][1]=rep(s[1]);

		ok[tot][2]=rep(s[2]);

	}

	for(R int i=1;i<=I;i++)

	{

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

		ok[++tot][0]=2;

		ok[tot][1]=rep(s[1]);

		ok[tot][2]=rep(s[2]);

	}

	for(R int i=1;i<=N;i++)

	{

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

		ok[++tot][0]=3;

		ok[tot][1]=rep(s[1]);

		ok[tot][2]=rep(s[2]);

	}

	for(R int i=1;i<=G;i++)

	{

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

		ok[++tot][0]=4;

		ok[tot][1]=rep(s[1]);

		ok[tot][2]=rep(s[2]);

	}

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

	int len=strlen(str+1);

	for(R int i=1;i<=len;i++)

		f[i][i][rep(str[i])]=true;

	for(R int i=len;i>=1;i--)

		for(R int j=i+1;j<=len;j++)

			for(R int k=i;k<j;k++)

				for(R int now=1;now<=tot;now++)

					if(f[i][k][ok[now][1]] and f[k+1][j][ok[now][2]])

						f[i][j][ok[now][0]]=true;

	if(f[1][len][1])putchar('W'),flg=true;

	if(f[1][len][2])putchar('I'),flg=true;

	if(f[1][len][3])putchar('N'),flg=true;

	if(f[1][len][4])putchar('G'),flg=true;

	if(!flg)puts("The name is wrong!");

}

巴特西

区间DP【p4290】[HAOI2008]玩具取名

Description

Input

Output

最新文章

热门文章