HAOI 2008 玩具取名

这是一个动态规划可行性判定问题。

设玩具名字的字符串为A，状态 F[i,j,k] 表示A中，从第i位到第j位，是否可以变换成字符k。

状态转移方程

F[i,j,k] = Or{F[i,l,k1] And F[l+1,j,k2] | i<=l<=j-1 且字符[k1k2]可以变换成k }

边界条件

F[i,i,A[i]]=true

目标结果

F[1,N,k]

/* 
 * Problem: HAOI2008 name
 * Author: Guo Jiabao
 * Time: 2009.4.20 8:53
 * State: Solved
 * Memo: 动态规划 可行性判定
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXL=201,MAXR=17;
const char Charset[5]="WING";
using namespace std;
int N,R[4],Rule[4][MAXR][2],A[MAXL];
bool F[MAXL][MAXL][4],Turn[4][4][4],noans=true;
inline int c2i(char c)
{
	if (c=='W') return 0;
	if (c=='I') return 1;
	if (c=='N') return 2;
	return 3;
}
void init()
{
	int i,j,a,b;
	char C[MAXL],c;
	freopen("name.in","r",stdin);
	freopen("name.out","w",stdout);
	memset(F,0,sizeof(F));
	memset(Turn,0,sizeof(Turn));
	for (i=0;i<4;i++)
		scanf("%d",&R[i]);
	for (i=0;i<4;i++)
	{
		for (j=1;j<=R[i];j++)
		{
			do c=getchar(); while (c==10||c==13);ungetc(c,stdin);
			c=getchar();a=c2i(c);
			c=getchar();b=c2i(c);
			Turn[a][b][i]=true;
		}
	}
	scanf("%s",C);i=1;
	for (char *p=C;*p;p++,i++)
		A[i]=c2i(*p);
	N=i-1;
}
void dynamic()
{
	int i,j,k,k1,k2,l;
	for (i=1;i<=N;i++)
		F[i][i][A[i]]=true;
	for (i=N;i>=1;i--)
		for (j=1;j<=N;j++)
			for (l=i;l<=j-1;l++)
				for (k=0;k<4;k++)
					for (k1=0;k1<4;k1++)
						for (k2=0;k2<4;k2++)
							F[i][j][k] |= Turn[k1][k2][k] && F[i][l][k1] && F[l+1][j][k2];
}
void solve()
{
	dynamic();
	for (int i=0;i<4;i++)
	{
		if (F[1][N][i])
		{
			printf("%c",Charset[i]);
			noans=false;
		}
	}
	if (noans)
		printf("The name is wrong!");
	printf("n");
}
int main()
{
	init();
	solve();
	return 0;
}

<div class="MainText">

<a href="http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=317" target="_blank">http://www.ruvtex.cn/cogs/problem/pdetail.php?pid=317</a>

<strong>玩具取名</strong>

[题目描述]

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

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

[输入]

第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。
接下来W行，每行两个字母,表示W可以用这两个字母替代。
接下来I行，每行两个字母,表示I可以用这两个字母替代。
接下来N行，每行两个字母,表示N可以用这两个字母替代。
接下来G行，每行两个字母,表示G可以用这两个字母替代。
最后一行一个长度不超过Len的字符串。表示这个玩具的名字。

[输出]
一行字符串，该名字可能由哪些字母变形而得到。（按照WING的顺序输出）
如果给的名字不能由任何一个字母变形而得到则输出“The name is wrong!”

[样例]

Input
```
1 1 1 1
  II
  WW
  WW
  IG
  IIII
```
Output
```
IN
```
[样例解释]
W可以变成II所以IIII可以缩成WW
IN均能变成WW所以WW又可以缩成I或者N
所以最终答案应该按照“WING”的顺序输出IN

[数据范围]
30%数据满足Len<=20，W、I、N、G<=6
100%数据满足Len<=200，W、I、N、G<=16

相关日志