[BZOJ1055] [HAOI2008] 장난감 이름[구간DP][상압]
처음에 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.