10pts,悬关!
查看原帖
10pts,悬关!
878013
_Supernova楼主2023/12/16 20:34
#include <bits/stdc++.h>
using namespace std;
const int maxn = 210;
int q[5];
string c, s;
bool can[5][5][5], dp[maxn][maxn][5], f;
int change (char x) {
	if (x == 'W') {
		return 1;
	}
	if (x == 'I') {
		return 2;
	}
	if (x == 'N') {
		return 3;
	}
	return 4;
}
int main(void) {
	ios::sync_with_stdio(false);
	for (int i = 1; i <= 4; ++i) {
		cin >> q[i];
	}
	for (int i = 1; i <= 4; ++i) {
		for (int j = 1; j <= q[i]; ++j) {
			cin >> c;
			can[i][change(c[0])][change(c[1])] = true;
		}
	} 
	cin >> s; 
	for (int i = 0; i < s.size(); ++i) {
		dp[i][i][change(s[i])] = true;
	}
	for (int l = 2; l <= s.size(); ++l) {
		for (int i = 1; i + l - 1 < s.size(); ++i) {
			int j = i + l - 1;
			for (int k = i; k < j; ++k) {
				for (int z = 1; z <= 4; ++z) {
					for (int z1 = 1; z1 <= 4; ++z1) {
						for (int z2 = 1; z2 <= 4; ++z2) {
							if (dp[i][k][z1] && dp[k + 1][j][z2] && can[z][z1][z2]) {
								dp[i][j][z] = true;
							}
						}
					}
				} 
			} 
		}
	}
	if (dp[0][s.size() - 1][1]) {
		f = true;
		cout << 'W';
	}
	if (dp[0][s.size() - 1][2]) {
		f = true;
		cout << 'I';
	}
	if (dp[0][s.size() - 1][3]) {
		f = true;
		cout << 'N';
	}
	if (dp[0][s.size() - 1][4]) {
		f = true;
		cout << 'G';
	}
	if (!f) {
		cout << "The name is wrong!";
	}
    return 0;
}
2023/12/16 20:34
加载中...