[BZOJ1055] [HAOI2008] 장난감 이름[구간DP][상압]

2347 단어
[제목 링크]
처음에 WA, DP가 무릎을 꿇은 줄 알았는데, 마지막에 해시 그룹이 작아진 걸 발견했어요...
dp[x][y]를 설정하면 [x, y]라는 구간을 간소화할 수 있는 가장 간단한 상태를 나타낸다. 그 중에서 상태는 0에서 15의 2진법으로 표시한다.
이동할 때 구간을 분할하여 두 구간의 상태를 얻은 다음에 대응하는 문자가 있는지 확인하면 된다.
경계 상태는 구간 길이가 1이고 구간 길이가 2이다.
/* Footprints In The Blood Soaked Snow */
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 205;

int n, W, I, N, G, hash[750], dp[maxn][maxn];
char str[maxn];

inline int gethash(char a, char b) {
	return (a - 'A') * 26 + (b - 'A');
}

inline char zip(int a) {
	if(a == 0) return 'W';
	if(a == 1) return 'I';
	if(a == 2) return 'N';
	if(a == 3) return 'G';
}

inline int getans(int s1, int s2) {
	int ans = 0;
	for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) {
		int a = s1 & (1 << i), b = s2 & (1 << j);
		if(!a || !b) continue;
		ans |= hash[gethash(zip(i), zip(j))];
	}
	return ans;
}

inline int dfs(int x, int y) {
	if(x == y) {
		if(str[x] == 'W') return dp[x][y] = 1;
		if(str[x] == 'I') return dp[x][y] = 2;
		if(str[x] == 'N') return dp[x][y] = 4;
		if(str[x] == 'G') return dp[x][y] = 8;
	}
	if(y - x + 1 == 2) return dp[x][y] = hash[gethash(str[x], str[y])];
	if(dp[x][y]) return dp[x][y];

	int ans = 0;
	for(int i = x; i < y; i++) {
		int l = dfs(x, i), r = dfs(i + 1, y);
		if(!l || !r) continue;
		ans |= getans(l, r);
	}
	return dp[x][y] = ans;
}

int main() {
	scanf("%d%d%d%d", &W, &I, &N, &G);
	for(int i = 1; i <= W; i++) {
		scanf("%s", str);
		hash[gethash(str[0], str[1])] |= 1;
	}
	for(int i = 1; i <= I; i++) {
		scanf("%s", str);
		hash[gethash(str[0], str[1])] |= 2;
	}
	for(int i = 1; i <= N; i++) {
		scanf("%s", str);
		hash[gethash(str[0], str[1])] |= 4;
	}
	for(int i = 1; i <= G; i++) {
		scanf("%s", str);
		hash[gethash(str[0], str[1])] |= 8;
	}
	scanf("%s", str); n = strlen(str);

	int ans = dfs(0, n - 1);
	if(!ans) {
		printf("The name is wrong!
"); return 0; } if(ans & 1) printf("W"); if(ans & 2) printf("I"); if(ans & 4) printf("N"); if(ans & 8) printf("G"); printf("
"); return 0; }

좋은 웹페이지 즐겨찾기