HAOI 2008 玩具取名

本文正體字版由OpenCC轉換

這是一個動態規劃可行性判定問題。

設玩具名字的字符串爲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

相關日誌