[BZOJ 3125] CITY 插头DP

传送门·Teleport!

题目大意

一个网格状地图被分割成N*M个块。
. 表示这个块可以通过
– 表示这个块只可以左右通过
| 表示这个块只可以上下通过
# 表示这个块不能通过
(从每个块只能走到其上下左右相邻的四个块)
那么把所以可以通过的块都经过且只经过一次并回到原地的方案数是多少?

解题报告

数据福利:

Input:
10 12
............
.......#....
.......#....
...|........
...|........
....--......
........#...
..#.....#...
....#.......
............
Output:
275026664

可怕的插头DP。。
关于插头DP是什么。。大家如果不知道可以先看看这个
基于连通性状态压缩的动态规划问题
题目要求找出一个环路走完全图的方案数
对于这道题，考虑每一行插头的状态,发现需要维护一个没有环的插头,然后在最后一个方格输出答案时把环接上就可以保证只有一个环了。
怎么保证插头合并时没有环路呢？考虑保存一个0,1,2组成的括号序列,每个半圆环路线在插头上的起点是左括号,在插头上的终点是右括号。那么怎样的一对插头上的相邻括号合并时不会产生环路呢？
分类讨论,发现右括号和左括号一定可以合并,如果左括号和左括号要合并,那么两个半环合并会形成一个新的半环,需要查询当前状态的括号序列中编号较大的左括号的相匹配右括号下标,并把这个右括号改成左括号,就可以继续维护括号序列不出问题。右括号和右括号合并类似。当相邻的左括号和右括号要合并时必然形成环路，除非统计答案，不能合并。
关于实现细节:
朴素的dp需要维护一个13位的三进制数长度数组，有几百万，光memset就可能T掉了。。打个表发现合法的括号序列(即合法状态数)不到6w,很小,手写哈希表维护。然后写着写着发现要查询相应括号序列中括号的匹配的括号的下标,心想反正打了哈希表就再懒一发。。于是又开了两个哈希表塞满括号序列便于查询。。。然后因为用哈希表维护状态,用四进制数代替三进制数后可以直接位运算,可能更快一些,就用四进制数代替了三进制数。

交上去一发T了,发现12*12的数据莫名爆掉,然后发现支持括号序列查询的哈希表开小了。。默默改大后就A了
JeremyGuo发现不用哈希表直接打出括号序列再dp会更快一些,但是他好像没写博客。。这里也给不了链接,反正那样也是可以过的。。
喂上写过的最长的dp

代码

#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long double LD;
typedef long long LL;


char g[20][20];
int bits[20], mask[20];
inline int getBit (int num, int i) {return (num&mask[i])>>bits[i-1];}
inline int setBit (int num, int i, int v) {return num-(getBit(num, i)<<bits[i-1])+(v<<bits[i-1]);}
int N, M;
void debug(int x, int bit) { // 蛤
    for(int i = 1; i<=bit; i++)
        printf("%d", getBit(x, i));
}
template<int HASH, class T> struct HashMap {
    int hash[HASH]; T data[HASH];
    void clear () {memset(hash, 0xff, sizeof hash);}
    int locate(int code) {
        int k = code%HASH;
        while(hash[k] != code) {
            if(hash[k] == -1) return k;
            k++; if(k >= HASH) k--;
        }
        return k;
    }
    void insert (int code, T val) {
        int p = locate(code);
        if(hash[p] == -1) hash[p]=code, data[p] = 0;
        data[p] += val;
    }
    T* query(int code) {
        int p;
        if(hash[p=locate(code)] == -1) return NULL;
        return data+p;
    }
};
const int HASHM = 67017, HASHX = 973497;
HashMap<HASHM, LL> mem[2]; HashMap<HASHX, char> lef, rig;
void dfs (int i, int s, int cnt) {
    if(i == M+1) {
        if(cnt != 0) return ;
        for(int i = 1; i<=M+1; i++)
            if(getBit(s, i) == 1) {
                int t = 1;
                for(int j = i+1; j<=M+1; j++) {
                    if(getBit(s, j) == 1) t++;
                    else if(getBit(s, j) == 2) t--;
                    if(!t) {rig.insert((s<<4)+i, j); break;}
                }
            } else if(getBit(s, i) == 2) {
                int t = 1;
                for(int j = i-1; j; j--) {
                    if(getBit(s, j) == 2) t++;
                    else if(getBit(s, j) == 1) t--;
                    if(!t) {lef.insert((s<<4)+i, j); break;}
                }
            }
        return ;
    }
    dfs(i+1, s<<2, cnt);
    dfs(i+1, (s<<2)+2, cnt+1);
    if(cnt) dfs(i+1, (s<<2)+1, cnt-1);
}

int main () {
    int lr = 0, lc = 0;
    scanf("%d%d", &N, &M);
    for(int i = 1; i<=N; i++)
        scanf("%s", g[i]+1);
    if(N == 1 && M == 1) {puts("1"); return 0;}
    bits[0] = 0;
    for(int i = 1; i<=13; i++)
        bits[i] = bits[i-1]+2;
    for(int i = 1; i<=13; i++)
        mask[i] = (1<<(i*2))-1;
    for(int i = 1; i<=N; i++)
        for(int j = 1; j<=M; j++)
            if(g[i][j] == '.') lr = i, lc = j;
    if(!lr && !lc) {puts("0"); return 0;}
    lef.clear(), rig.clear();
    dfs(0, 0, 0);

    int src = 0, dp = 1;
    mem[src].clear(); mem[src].insert(0, 1);
    for(int row = 1; row<=N; row++) {
        for(int col = 1; col<=M; col++) {
            if(row == lr && col == lc) break;
            mem[dp].clear();
            for(int i = 0; i<HASHM; i++) {
                if(mem[src].hash[i] == -1) continue;
                int s = mem[src].hash[i], ld = getBit(s, col), rd = getBit(s, col+1);
                LL val = mem[src].data[i];
                if(ld == 1 && rd == 2) continue ; //环合并，无解
                if(g[row][col] == '#') { //空转移
                    if(ld == 0 && rd == 0)
                        mem[dp].insert(s, val);
                } else if(g[row][col] == '|' && row != N) {
                    if(ld == 0 && rd != 0)
                        mem[dp].insert(setBit(setBit(s, col, rd), col+1, 0), val);
                } else if(g[row][col] == '-') {
                    if(ld != 0 && rd == 0 && col != M)
                        mem[dp].insert(setBit(setBit(s, col, 0), col+1, ld), val);
                } else if(ld == 0 && rd == 0)
                    mem[dp].insert(setBit(setBit(s, col, 1), col+1, 2), val);
                else if(ld && rd) { // 不同环合并
                    char * r;
                    if(ld == 1 && rd == 1 && (r=rig.query((s<<4)+col+1)) != NULL)
                        mem[dp].insert(setBit(setBit(setBit(s, col, 0), col+1, 0), *r, 1), val);
                    else if(ld == 2 && rd == 2 && (r=lef.query((s<<4)+col)) != NULL)
                        mem[dp].insert(setBit(setBit(setBit(s, col, 0), col+1, 0), *r, 2), val);
                    else if(ld == 2 && rd == 1)
                        mem[dp].insert(setBit(setBit(s, col, 0), col+1, 0), val);
                    else if(lr == row && lc == col)
                        mem[dp].insert(setBit(setBit(s, col, 0), col+1, 0), val);
                } else { //只剩一个为0一个有插头
                    int r = ld+rd;
                    if(col != M) mem[dp].insert(setBit(setBit(s, col, 0), col+1, r), val);
                    if(row != N) mem[dp].insert(setBit(setBit(s, col, r), col+1, 0), val);
                }
            }
            std :: swap(src, dp);
        }
        if(row == lr) break; //保留答案
        //否然换行
        mem[dp].clear();
        for(int i = 0; i<HASHM; i++) {
            if(mem[src].hash[i] == -1) continue;
            int s = mem[src].hash[i]; LL val = mem[src].data[i];
            if(getBit(s, M+1) == 0) mem[dp].insert((s<<bits[1])&mask[M+1], val);
        }
        std :: swap(src, dp);
    }
    int code = setBit(0, lc, 1)+setBit(0, lc+1, 2);
    LL * pos = mem[src].query(code);
    if(pos == NULL) printf("0\n");
    else cout << *pos << '\n';
}