[luogu4290 HAOI2008]玩具取名(DP)

Solution

裸区间DP

Code

#include <map>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

using namespace std;

inline int read() {

	int x=0,f=1;char c=getchar();

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

	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int tot,len;

map <char,int> M;

char str[]="!WING",ch[300];

int num[5],sc[300][3],f[300][300][5];

int main() {

	F(i,1,4) M[str[i]]=i;

	F(i,1,4) num[i]=read();

	F(i,1,4) F(j,1,num[i]) sc[++tot][0]=i,scanf("%s",ch+1),sc[tot][1]=M[ch[1]],sc[tot][2]=M[ch[2]];

	scanf("%s",ch+1);len=strlen(ch+1);

	F(i,1,len) f[i][i][M[ch[i]]]=1;

	F(L,1,len) F(i,1,len-L+1) {

		int j=i+L-1;

		F(k,i,j-1) F(x,1,tot)

			f[i][j][sc[x][0]]|=f[i][k][sc[x][1]]&f[k+1][j][sc[x][2]];

	}

//	F(i,1,len) F(j,i,len) F(k,1,4) cout<<i<<" "<<j<<" "<<k<<" "<<f[i][j][k]<<endl;

	bool flag=0; F(i,1,4) if(f[1][len][i]) putchar(str[i]),flag=1;

	if(!flag) puts("The name is wrong!");

	return 0;

}

巴特西

[luogu4290 HAOI2008]玩具取名(DP)

Solution

Code

最新文章

热门文章