HDU_1964
这个题目只需要把求回路数量的dp方程改写成取最优解的dp方程即可。
更多和插头dp相关的题目可以参考胡浩的博客：。
#include#include #define MAXD 15#define HASH 30007#define SIZE 1000010#define INF 0x3f3f3f3fint N, M, code[MAXD], ch[MAXD], maze[MAXD][MAXD], rcost[MAXD][MAXD], dcost[MAXD][MAXD];char b[50];struct Hashmap{ int head[HASH], next[SIZE], state[SIZE], f[SIZE], size; void init() { memset(head, -1, sizeof(head)); size = 0; } void push(int st, int ans) { int i, h = st % HASH; for(i = head[h]; i != -1; i = next[i]) if(state[i] == st) { if(ans < f[i]) f[i] = ans; return ; } state[size] = st, f[size] = ans; next[size] = head[h]; head[h] = size ++; }}hm[2];void decode(int *code, int m, int st){ int i; for(i = m; i >= 0; i --) { code[i] = st & 7; st >>= 3; }}int encode(int *code, int m){ int i, cnt = 0, st = 0; memset(ch, -1, sizeof(ch)); ch[0] = 0; for(i = 0; i <= m; i ++) { if(ch[code[i]] == -1) ch[code[i]] = ++ cnt; code[i] = ch[code[i]]; st <<= 3; st |= code[i]; } return st;}void init(){ int i, j, k; gets(b), sscanf(b, "%d%d", &N, &M); memset(maze, 0, sizeof(maze)); for(i = 1; i <= N; i ++) for(j = 1; j <= M; j ++) maze[i][j] = 1; gets(b); for(i = 1; i < 2 * N; i ++) { gets(b); if(i & 1) { for(j = 1, k = 2; k < 2 * M; j ++, k += 2) rcost[(i + 1) >> 1][j] = b[k] - '0'; } else { for(j = 1, k = 1; k < 2 * M; j ++, k += 2) dcost[i >> 1][j] = b[k] - '0'; } } gets(b);}void shift(int *code, int m){ int i; for(i = m; i > 0; i --) code[i] = code[i - 1]; code[0] = 0;}void dpblank(int i, int j, int cur){ int k, left, up, t; for(k = 0; k < hm[cur].size; k ++) { decode(code, M, hm[cur].state[k]); left = code[j - 1], up = code[j]; if(left && up) { if(left == up) { if(i == N && j == M) { code[j - 1] = code[j] = 0; shift(code, M); hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]); } } else { code[j - 1] = code[j] = 0; for(t = 0; t <= M; t ++) if(code[t] == up) code[t] = left; if(j == M) shift(code, M); hm[cur ^ 1].push(encode(code, M), hm[cur].f[k]); } } else if(left || up) { if(maze[i][j + 1]) { code[j - 1] = 0, code[j] = left + up; hm[cur ^ 1].push(encode(code, M), hm[cur].f[k] + rcost[i][j]); } if(maze[i + 1][j]) { code[j - 1] = left + up, code[j] = 0; if(j == M) shift(code, M); hm[cur ^ 1].push(encode(code, M), hm[cur].f[k] + dcost[i][j]); } } else { if(maze[i][j + 1] && maze[i + 1][j]) { code[j - 1] = code[j] = 13; hm[cur ^ 1].push(encode(code, M), hm[cur].f[k] + rcost[i][j] + dcost[i][j]); } } }}void solve(){ int i, j, cur = 0, ans = INF; hm[cur].init(); hm[cur].push(0, 0); for(i = 1; i <= N; i ++) for(j = 1; j <= M; j ++) { hm[cur ^ 1].init(); dpblank(i, j, cur); cur ^= 1; } for(i = 0; i < hm[cur].size; i ++) if(hm[cur].f[i] < ans) ans = hm[cur].f[i]; printf("%d\n", ans);}int main(){ int t; gets(b), sscanf(b, "%d", &t); while(t --) { init(); solve(); } return 0;}