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