首页 > 代码库 > [BZOJ 1055] [HAOI2008] 玩具取名 【记忆化搜索】
[BZOJ 1055] [HAOI2008] 玩具取名 【记忆化搜索】
题目链接：BZOJ - 1055
题目分析
这种类似区间 DP 的记忆化搜索都是很相近的，比如字符串压缩和字符串扩展都差不多。
都是将现在 Solve 的区间分成子区间，再求解子区间。
这道题 Solve(l, r, x) 求能否将 [l, r] 的区间还原成 x ，那么就将它分成两段，看是否能左段变成 p ， 右段变成 q。 （x 能变成 pq）
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int MaxL = 200 + 5;char Ch[5] = {‘W‘, ‘I‘, ‘N‘, ‘G‘};int len;int n[5], f[MaxL][MaxL][5];char S[MaxL];bool Tr[5][5][5];int Solve(int l, int r, int x) { if (f[l][r][x] != 0) return f[l][r][x]; if (l == r) { if (S[l] == Ch[x]) { f[l][r][x] = 1; return 1; } else { f[l][r][x] = -1; return -1; } } for (int i = l; i <= r - 1; ++i) { for (int j = 0; j < 4; ++j) { for (int k = 0; k < 4; ++k) { if (!Tr[x][j][k]) continue; if (Solve(l, i, j) == 1 && Solve(i + 1, r, k) == 1) { f[l][r][x] = 1; return 1; } } } } f[l][r][x] = -1; return -1;}int GetNum(char c) { for (int i = 0; i < 4; ++i) if (c == Ch[i]) return i; return -1;}int main() { for (int i = 0; i < 4; ++i) scanf("%d", &n[i]); char cc[3]; for (int i = 0; i < 4; ++i) { for (int j = 1; j <= n[i]; ++j) { scanf("%s", cc); Tr[i][GetNum(cc[0])][GetNum(cc[1])] = true; } } scanf("%s", S + 1); len = strlen(S + 1); bool Flag = false; for (int i = 0; i < 4; ++i) if (Solve(1, len, i) == 1) { printf("%c", Ch[i]); Flag = true; } if (!Flag) printf("The name is wrong!"); printf("\n"); return 0;}
[BZOJ 1055] [HAOI2008] 玩具取名 【记忆化搜索】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。