bzoj1055,懒得复制，戳我戳我

Solution:

• 区间动规（以后开始动规会在solution前面标注是啥动规
• 我觉的这道题挺难想了，但其实状态定义了一下子就出来了（还是不行啊）
• 我们定义状态\(dp[i][j][sta]\)，表示在\(i\)到\(j\)区间可不可以合成字符\(sta\)，这里我们用\(1\)表示\(W\)，\(2\)表示\(I\)依次类推
• 转移方程就很简单了:（注意有一个是\(1\)就是\(1\)，然后可以\(break\)了） $$dp[i][j][sta]=max((dp[i][k][ left ]),(dp[k+1][j][ right] ))$$.
  
  或者说$$dp[i][j][sta]=((dp[i][k][ left ])&(dp[k+1][j][ right] ))$$
• \(left\)表示某个合成\(sta\)的方法中左边那个字符代表的数字，\(right\)就是右边那个

Attention:

• 注意无解情况输出

Code:

//It is coded by Ning_Mew on 5.10

#include<bits/stdc++.h>

using namespace std;

const int maxn=207;

int n[5],ll=0;

int s[10][20][5];

int goal[maxn];

string ss;

int dp[maxn][maxn][10];

int num[30];

int main(){

  scanf("%d%d%d%d",&n[1],&n[2],&n[3],&n[4]);

  num['W'-'A'+1]=1;num['I'-'A'+1]=2;

  num['N'-'A'+1]=3;num['G'-'A'+1]=4;

  for(int i=1;i<=4;i++){

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

      cin>>ss;

      s[i][j][1]=num[ss[0]-'A'+1];

      s[i][j][2]=num[ss[1]-'A'+1];

    }

  }

  cin>>ss;ll=ss.length();

  for(int i=0;i<ll;i++){

    dp[i][i][ num[ss[i]-'A'+1] ]=1;

    goal[i]=num[ss[i]-'A'+1];

  }

  for(int len=2;len<=ll;len++){

    for(int i=0;i<=ll-len;i++){

      int ss=i,tt=i+len-1;

      for(int j=ss;j<=tt-1;j++){//中间的断点

	for(int sta=1;sta<=4;sta++){

	  for(int k=1;k<=n[sta];k++){

	    int ll=s[sta][k][1],rr=s[sta][k][2];

	    if(dp[ss][j][ll]==1 && dp[j+1][tt][rr]==1){dp[ss][tt][sta]=1;break;}

	  }

	}

      }

    }

  }

  bool out=false;

  for(int i=1;i<=4;i++){

    if(dp[0][ll-1][i]){

      if(i==1)printf("W"),out=true;if(i==2)printf("I"),out=true;

      if(i==3)printf("N"),out=true;if(i==4)printf("G"),out=true;

    }

  }

  if(!out)printf("The name is wrong!");printf("\n");

  return 0;

}