某岛

… : "…アッカリ～ン . .. . " .. .
September 24, 2015

插头 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

Posted by xiaodao
Category: 算法收集

« | »

  • Archives

    open all | close all