插头 DP 大字典

Overview

课文:http://www.cnblogs.com/kuangbin/archive/2012/10/02/2710343.html
http://notonlysuccess.me/?p=931

本质上只是状态里保存了连通性信息的状态压缩 DP,因而也会受到和状态压缩 DP 一样的局限。
通常状态和转移错综复杂,而且一旦出错难以 debug,需要系统的学习和整理。
学习之前要先会轮廓线 DP(至少得会用轮廓线 DP 做多米诺骨牌完美覆盖问题)。

一些轮廓线 DP 的好题推荐:

好了以下是正文。

多条回路

主要两大模型:路径问题,和染色问题。先来看各种路径模型。
这类问题实际上不需要保存状态的连通性信息,只需要用 01 状态记录轮廓线上插头是否存在,因而严格意义上只能算是轮廓线 DP。不过因为和其他路径问题紧密相关,可以拿来参照学习,里面的技巧也出来先了其他问题中。

注意 L 型的骨牌可以旋转,考虑加维,记录插头是否可以转弯。

一条回路

最经典的模型,可以比较一下括号表示,和最小表示,因为最小表示解决的问题更多,转移写起来也更简单。

最小表示:

// _M 表示多少位一压、与插头的种类最大种类数有关。。有时需要维护其他状态,它们的占位可能和 _M 不一样,用 _M2 表示,注意新的状态可能不参与 roll()。
const int M = 12, _M = 3; 

// 以一般 M+1 个插头为例,bb 开到 M+2,是因为一般向的插头问题,我们在生成新插头时,希望生成一个和所有其他插头都不一样的插头。
// 这个数字一般用 m+1 是安全的。

int b[M+1], bb[M+2];  

LL encode(){
    FLC(bb, -1); int n = 1; REP(i, n) bb[i] = i; LL s = 0;
    DWN(i, m+1, 0){
        if (!~bb[b[i]]) bb[b[i]] = n++;
        s <<= _M; s |= bb[b[i]];
    }
    return s;
}
 
void decode(int s){
    REP(i, m+1){
        b[i] = s & _U(_M); s >>= _M;
    }
}

手写哈希表:

const int Prime = 9979, MaxSize = 1 << 18; // 难以捉摸的经验数字。
int d; // 全局变量大法好。
struct hashTable{
    int state[MaxSize]; int key[MaxSize];
    int hd[Prime], nxt[MaxSize], sz;

    void clear(){
        sz = 0;
        FLC(hd, -1);
    }
    void push(){
        int s = encode();
        int x = s % Prime; // 这附近可以加剪枝。。。
        for (int i=hd[x];~i;i=nxt[i]) if (state[i] == s){
            key[i] += d;
            return;
        }
        state[sz] = s; key[sz] = d;
        nxt[sz] = hd[x]; hd[x] = sz;
        ++sz;
        assert(sz < MaxSize);
        return;
    }
    void roll(){
        REP(ii, sz) state[ii] >>= _M;
    }
    void display(int ii){
        decode(state[ii]);
        REP(i, m) cout << b[i] << " ";
        cout << ": " << key[ii];
        cout << endl;

    }
} H[2]; int src, des;
  • Ural 1519. Formula 1
  • 母题。
    http://acm.timus.ru/problem.aspx?space=1&num=1519

  • HDU 1964. Pipes
  • 这题不再算方案数,而是算路径的最大权值,修改下 HashTable 就好了

  • FZU 1977. Pandora adventure
  • http://acm.fzu.edu.cn/problem.php?pid=1977
    很多题输入的时候会对格子进行区分,比如必须经过的点、可以经过的点、和障碍。
    比如这个题。

  • 第九届北航程序设计大赛现场决赛 – 晴天小猪当导游
  • http://user.qzone.qq.com/251815992/blog/1442232794
    再上题的基础上,每个格子所能继承和发出的插头也要考虑。

  • ProjectEuler 393. Migrating ants
  • https://projecteuler.net/problem=393
    对于每一个有 m 条回路的方案,对答案的贡献是 2^m。因而需要记录回路条数?
    显然不需要,只要在转移的时候改一下系数就好了。因为需要区分回路合并的时刻,因而用多条回路的模型是不行的。
    这是一种很重要的思想。例如、下面的很多简单路径问题,由于出发点和终止点固定,都可以划归为一条回路问题。

简单路径

不再是回路,需要多加状态记录独立插头生成的数目,而且插头不再总是成对出现。

对于加状态,如果只是加比较简单的状态,可以开在 Hash 表下标里,比较方便。
复杂的话就和联通信息一起放在 Hash 表里,可以多开数组,也可以一起压缩到状态里,后者 Roll() 的时候要分开。

迷宫问题

染色模型

  • Topcoder SRM 312. Div1 CheapestIsland
  • UVA 10572 black&white
  • HDU 3633. Black and white

综合问题

神题

下面是一些个人感觉非常 tasty 的题目,他们要么是简洁但又艰深的问题,要么做完以后能给予我很大启发。

—————— To do list …

NOI 2010 day2 旅行路线
SPOJ CAKE3. Delicious Cake