HAOI 2008 玩具取名

This post is written in Chinese. Please consider using Google Translate

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

设玩具名字的字符串为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

Related posts