[ HAOI 2008 ] 玩具取名

\(\\\)

\(Description\)

在一个只有\(W,I,N,G\)的字符集中，给出四个字符的若干映射，每个映射为一个字符映射到两个字符，现给你一个假定由一个字符经过多次映射产生的字符串，问将其还原成一个字符，可以还原成四类字符的哪几个。

每个字符的映射集合大小不超过\(16\)，给出的映射后字符串长度不超过\(200\)

\(\\\)

\(Solution\)

注意到每次是两个字符合成一个字符，不妨考虑每一个字符合成的过程。
可达性\(DP\)。设\(f[i][j][k]=0/1\)表示闭区间\([i,j]\)能否合成一个字符\(k\)，显然边界有\(f[i][i][num[i]]=1\)
转移就是基本的区间\(DP\)的形式，枚举长度，端点，检查左右两端能否合并即可。

基本形式知道了做题还是不会往题上套看来姿势还是要速度涨起来

\(\\\)

\(Code\)

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 210

#define R register

#define gc getchar

using namespace std;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

char s[N];

bool f[N][N][4];

int n[4],tot,num[N],trs[4][20][2];

inline int fuc(char x){

  return (x=='W'?0:(x=='I'?1:(x=='N'?2:3)));

}

int main(){

  for(R int i=0;i<=3;++i) n[i]=rd();

  char c=gc();

  for(R int i=0;i<=3;++i)

    for(R int j=1;j<=n[i];++j){

      while(!isupper(c)) c=gc();

      trs[i][j][0]=fuc(c);

      trs[i][j][1]=fuc(gc()); c=gc();

    }

  while(!isupper(c)) c=gc();

  num[1]=fuc(c);

  scanf("%s",s);

  int slen=strlen(s);

  for(R int i=0;i<slen;++i) num[tot=(2+i)]=fuc(s[i]);

  for(R int i=1;i<=tot;++i) f[i][i][num[i]]=1;

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

    for(R int l=1,r;l<=tot-len+1;++l){

      r=l+len-1;

      for(R int k=l;k<r;++k)

        for(R int i=0;i<=3;++i)

          for(R int j=1;j<=n[i];++j)

            f[l][r][i]|=f[l][k][trs[i][j][0]]&&f[k+1][r][trs[i][j][1]];

    }

  bool fl=0;

  for(R int i=0;i<=3;++i) if(f[1][tot][i])fl=1;

  if(!fl){puts("The name is wrong!");return 0;}

  if(f[1][tot][0]) printf("W");

  if(f[1][tot][1]) printf("I");

  if(f[1][tot][2]) printf("N");

  if(f[1][tot][3]) printf("G");

  return 0;

}

巴特西

[ HAOI 2008 ] 玩具取名

\(Description\)

\(Solution\)

\(Code\)

最新文章

热门文章