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

相關日誌