某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。
现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。
算法：区间dp；
这题是很简单的区间dp；（HA动规真不少）
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<ctime> #include<algorithm> #include<cstdlib> #include<map> #include<set> #include<vector> #include<queue> #include<cmath> using namespace std; #define FILE "dealing" #define LL long long #define up(i,j,n) for(int i=j;i<=n;i++) #define pii pair<int,int> #define piii pair<int,pii > template<typename T> inline bool chkmin(T &a,T b){return a>b?a=b,true:false;} template<typename T> inline bool chkmax(T &a,T b){return a<b?a=b,true:false;} namespace IO{ char *fs,*ft,buf[1<<15]; inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;} inline int read(){ LL x=0;int ch=gc();bool f=0; while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();} return f?-x:x; } }using namespace IO; namespace OI{ const int maxn(101000); char flag[5]; int t[300]; int f[210][210][10]; int g[5][5][5]; char s[210];int n; void init(){ flag[1]='W',flag[2]='I',flag[3]='N',flag[4]='G'; t['W']=1,t['I']=2,t['N']=3,t['G']=4; int cnt[6]; char ch[6]; up(i,1,4)scanf("%d",&cnt[i]); up(i,1,4)while(cnt[i]--){ scanf("%s",ch); g[i][t[ch[0]]][t[ch[1]]]=1; } scanf("%s",s+1); } void slove(){ init(); n=strlen(s+1); up(i,1,n)f[i][i][t[s[i]]]=1; int j; up(L,2,n)up(i,1,n-L+1){ j=i+L-1; up(k,i,(j-1))up(t,1,4)up(x,1,4){ if(f[i][j][t])break; up(y,1,4)if(f[i][k][x]&&f[k+1][j][y]&&g[t][x][y]){f[i][j][t]=1;break;}//转移比较暴力 } } bool f1=0; if(f[1][n][1]){cout<<"W";f1=1;} if(f[1][n][2]){cout<<"I";f1=1;} if(f[1][n][3]){cout<<"N";f1=1;} if(f[1][n][4]){cout<<"G";f1=1;} if(!f1)cout<<"The name is wrong!"; cout<<endl; return; } } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); using namespace OI; slove(); return 0; }