Bzoj 1055 玩具取名（区间DP）

题面

题解

字符很麻烦，不妨用数字代替（比如1代表'W'）

const char c[5] = {0, 'W', 'I', 'N', 'G'};

接着，像这种两个子串可以合并成另一个子串的题可以考虑区间$DP$

设$bool$数组$f_{i,j,k}$表示区间$[l,r]$能否合成单个字符$c_k$

于是就可以套区间$DP$的板子了

#include <map>

#include <cstdio>

#include <cstring>

#include <algorithm>

using std::min; using std::max;

using std::sort; using std::swap;

using std::unique; using std::lower_bound;

using std::map;

typedef long long ll;

template<typename T>

void read(T &x) {

    int flag = 1; x = 0; char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }

    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;

}

const int Len = 2e2 + 10, _ = 5;

const char c[5] = {0, 'W', 'I', 'N', 'G'};

char s[Len]; bool p, f[Len][Len][_];

int num[_], list[Len][_], tot, len;

int check(char x) { for(int i = 1; i <= 4; ++i) if(x == c[i]) return i; }

int main () {

	for(int i = 1; i <= 4; ++i) read(num[i]);

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

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

			char ss[5]; scanf("%s", ss);

			list[++tot][0] = i;

			list[tot][1] = check(ss[0]);

			list[tot][2] = check(ss[1]);

		}

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

	for(int i = 1; i <= len; ++i) f[i][i][check(s[i])] = true;

	for(int k = 1; k <= len; ++k)

		for(int i = 1; i + k <= len; ++i) {

			int j = i + k;

			for(int p = i; p < j; ++p)

				for(int l = 1; l <= tot; ++l)

					if(f[i][p][list[l][1]] && f[p + 1][j][list[l][2]])

						f[i][j][list[l][0]] = true;

		}

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

		if(f[1][len][i]) putchar(c[i]), p = true;

	if(!p) printf("The name is wrong!");

	puts("");

	return 0;

}

巴特西

Bzoj 1055 玩具取名（区间DP）

题面

题解

最新文章

热门文章