http://acm.bnu.edu.cn/v3/problem_show.php?pid=15645
http://cojs.tk/cogs/problem/problem.php?pid=1514

Brief description:

疯狂火箭（Rocket Mania）是幻想游戏系列中我最喜欢的游戏之一。在这个游戏中，左边有一些火柴，右边有一些火箭。在中间，有许多种类的带有导火索的格子。这些导火索可以被旋转0，90，180或270度。为了发射火箭，必须用导火索形成一条从火柴到火箭的连续通道。当一条完整的通路建立的时候，连接着火柴的所有火箭都将被发射。

你的任务是，给出初始情况，旋转一些导火索，使点燃某一根火柴后，发射的火箭数量尽量多。

Analysis:

算法分析
确立状态：按照从左到右，从上到下的顺序依次考虑每一个格子，我们需要记录每个插头是否已经点燃以及它们之间的连通情况．因此状态为 f(i, j, S, fired) 表示转移完(i, j)，轮廓线上10个插头的连通性为S(把每个插头是否存在记录在S中), 10个插头是否被点燃的2进制数fired的状态能否达到．
那么最后的答案为所有可以达到的状态 f(i, j, S, fired) 中 Ones[fired]的最大值，其中 Ones[x]表示二进制数 x 的 1 的个数。
状态转移：依次枚举每一个格子的旋转方式 (最多4种)，根据当前格子是否可以与上面的格子和左边的格子通过插头连接起来分情况讨论，O(m) 扫描计算出新的状态．前面的题目我们已经很详细地介绍过棋盘模型的问题的转移方法，这里不再赘述．

独立插头，插头的转移十分灵活，且至多会出现 m 个不同的独立插头，因而优先考虑最小表示法描述上面的状态 S。
然后还需要记录，每个位置的插头是否处于引燃的状态（也可以记录每个种类的插头是否处于引燃状态，虽然转移上常数可能会小、但是统计答案以及剪枝时会比较麻烦。）

用类似 HDU 5374. Tetris 的方法，用四位二进制数，预处理出每种插头的旋转。

void Init(){
    
    // 1 Left
    // 2 Up
    // 4 Down
    // 8 Right
    
    // '.'
    Pattern[0].PB(0);
    // '-'
    Pattern[1].PB(1|8); Pattern[1].PB(2|4);
    // 'L'
    Pattern[2].PB(2|8); Pattern[2].PB(8|4); Pattern[2].PB(4|1); Pattern[2].PB(1|2);
    // 'T'
    int U = 15;
    Pattern[3].PB(U^1); Pattern[3].PB(U^2); Pattern[3].PB(U^4); Pattern[3].PB(U^8);
    // '+';
    Pattern[4].PB(U);
}

转移时各种讨论、看上插头和左插头的状态得到下插头和右插头的状态。

                ECH(it, Pattern[A[i][j]]){
                
                    decode(H[src].state[ii]);
                    
                    int p = *it;
                    
                    int lt = b[j], up = b[j+1];
                    bool lt2 = _1(p,0) && lt, up2 = _1(p,1) && up; 
//需要同时判断格子所在的插头和状态所在的插头同时为真。
                    bool BurN = ((lt2 && _1(BurNing, j)) || (up2 && _1(BurNing, j+1)));
//并且如果有一处引燃，则生成的新插头也引燃并且如果发生合并则合并过后的插头也。
                    
                    b[j] = b[j+1] = 0;
                    BurNing &= ~_1(j);
                    BurNing &= ~_1(j+1);
                    
                    int t;

                    if (lt2 && up2){ // 合并插头，如果有一个引燃则将所有位置等于这两个插头的状态全部置于引燃。
                        t = up;
                        REP(k, m+1) if (b[k] == lt || b[k] == up){
                            if (BurN) BurNing |= _1(k);
                            b[k] = t;
                        }
                    }
                    else if (lt2 | up2){ 
                        if (lt2) t = lt; else t = up;
                    }
                    else{ // 注意最多会产生 m 个插头，因而新产生的插头要填 m+1。
                        t = m+1;
                    }
                    
                    if (_1(p,2)){ // 是否产生下插头
                        b[j] = t;
                        if (BurN) BurNing |= _1(j);
                    }
                    
                    if (_1(p,3) && j != m-1){ // 是否产生右插头
                        b[j+1] = t;
                        if (BurN) BurNing |= _1(j+1);
                    }
                    
                    if (!BurNing) continue; // Cut-1
                
                    RST(bb); REP(k, m+1) if (b[k]) ++bb[b[k]];
                    REP(k, m+1) if (bb[b[k]] == 1 && !_1(BurNing, k)) b[k] = 0; // Cut-2
                    
                    LL s = encode(); _des.push_back(s);
                    if (count_bits(BurNing) > best){
                        best = count_bits(BurNing);
                        critical = s;
                    }
                }

如果直接按照上面的思路作动态规划，Sample也需要运行> 60s，实在令人无法满意．优化，势在必行．如何通过剪枝优化来减少扩展的状态总数，尽可能舍去无效状态成为了现在所面临的问题：
剪枝通常可以分为两类：一．可行性剪枝，即将无论之后如何决策，都不可能满足题目要求的状态剪掉；二．最优性剪枝，即对于最优性问题，将不可能成为最优解的状态给剪掉．我们从这两个角度入手来考虑问题：

• 剪枝一：如果轮廓线上所有的插头全部都未被点燃，那么最后所有的火箭都不可能发射，所以这个状态可以舍去．这个剪枝看上去非常显然，对于大部分数据却可以剪掉近乎一半的状态．
• 剪枝二：如果轮廓线上有一个插头p，它没有被火柴点燃且没有其它的插头与它连通，那么这个插头可以认为是“无效”插头．因为即使这个插头所在的路径以后会被点燃而可以发射某个火箭，那么一定存在另一条路径可以不经过这个插头而发射火箭，如图．这种情况下将插头设置为不存在．这是最重要的一个剪枝，大部分数据的状态总数可以缩小七八倍，甚至十几倍．

剪枝三：这是一个最优性问题，我们考虑最优性剪枝：对于一个格子(i, j)的两个状态 (S0, Fired0)， (S1, Fired1)，如果第一个状态的每一个存在的插头在第二个状态中不仅存在而且都被点燃，那么无论以后如何决策，第二个状态点燃的火箭个数不会少于第一个状态，这样我们就可以果断地舍去第一个状态．对于每一个(i, j)，选择Ones[Fired]最多的一个状态Best，如果一个状态一定不比Best好，就可以舍去．

• 剪枝四：从边界情况入手，边界状态非常特殊，也非常容易导致产生无效状态．分析一下，转移完最后一列的某个格子(i, 6)后，如果I类插头中某个插头p没有被点燃，并且II类插头中没有插头与它连通，那么这个插头就成了“无效”插头．

比较以上四种剪枝的效果，由于不同的棋盘初始状态扩展的状态总数差异较大，因此选取10组不同的棋盘初始状态来测试扩展状态的总数．10组数据大致分布如下：Test 1~4依次为全部“—”，“L”,“T”，“+”，Test 5为奇数行“L”，偶数行为空，Test 6为“L”，“T”交替．Test 7~10为随机数据，“L”，“T”分布较多，Test 10的“—”较多．

注意，上面的剪枝三，如果对每个状态都找是否有一个状态可以完整覆盖的话，代价太大。
因此采用的是一种折衷的策略，只记录 Fired 最多的状态，进行剪枝。

https://gist.github.com/lychees/085c994a7bedb29154bd

Posted by xiaodao
Category: 日常
Tags: 插头DP, 独立插头