洛谷 P4290 [HAOI2008]玩具取名

思路

博客半年没更新了，来更新个博文吧

在\(dsr\)聚聚博客的帮助下，我用半个上午和一个中午的时间苟延残喘地完成了这道题

先是读题目读大半天，最后连个样例都看不懂

之后又是想思路，实在想不出来，便去看了\(dsr\)学长的博客，发现是一道区间\(DP\)题

我们用\(f[i][j][k]\)来表示\(i\)、\(j\)这个区间能否压缩成为\(k\)这个字符

基本框架为

枚举长度len

	枚举起点i

		计算终点j

		枚举中点k

			起点到中点的check

				中点到终点的check

					转移

字符不多，所以是可以跑过去的

代码

#include <cstdio>

#include <string>

#include <cstring>

#include <iostream>

using namespace std;

inline int read() {

	char c = getchar();

	int x = 0, f = 1;

	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;

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

	return x * f;

}

int le[5], f[211][211][5];

bool z[5][5][5], flag;

char yuan[5], s[5], ss[211];

int calc(char w) {

	if(w == 'W') return 1;

	if(w == 'I') return 2;

	if(w == 'N') return 3;

	if(w == 'G') return 4;

}

int main() {

	strcpy(yuan, " WING");

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

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

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

			scanf("%s", &s);

			z[i][calc(s[0])][calc(s[1])] = 1;

		}

	}

	scanf("%s", ss + 1);

	int n = strlen(ss + 1);

	for(int i = 1; i <= n; i++) f[i][i][calc(ss[i])] = 1;

	for(int len = 1; len < n; len++) {//枚举长度

		for(int i = 1; i <= n; i++) {//枚举起点

			int j = i + len;

			if(j > n) break;//终点

			for(int k = i; k < j; k++) {//中点

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

					if(f[i][k][ip]) {

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

							if(f[k + 1][j][jp]) {

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

									if(z[kp][ip][jp] == 1) {

										f[i][j][kp] = 1;

									}

								}

							}

						}

					}

				}

			}

		}

	}

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

		if(f[1][n][i]) {

			flag = 1;

			printf("%c", yuan[i]);

		}

	}

	if(!flag) cout << "The name is wrong!\n";

	return 0;

}