\(>Topcoder \space Srm \space 671 \space Div2 \space 1000 \space BearDestroysDiv2<\)

題目大意 : 有一個 \(W \times H\) 的網格，每一格上有一棵樹和一個隨機字母 \(S\) 或 \(E\) ，有一只熊在左上角，按從上到下從左到右的順序遍歷每一行每一列，如果其遇到一棵可以推倒的樹，就盡可能按照字母表示的方向 (向下，向右) 推倒它，然后其推倒方向的下一棵樹就不能被推倒了，同時樹不能被推倒在邊界之外，求對于所有可能的網格圖，樹的被推倒個數總和對 \(Mod\) 取模的值 。
\(1 \leq W \leq 7 \ ,1 \leq H \leq 40\)

解題思路 :

觀察到 \(W\) 比較小，不妨對列進行狀態(tài)壓縮，又因為直接狀壓每一列后效性很難討論，所以維護輪廓線來 \(dp\) 轉移.

設 \(f[i][r][j][s]\) 表示第 \(i\) 行維護的輪廓線斷點在 \(r\), 輪廓線上的點的狀態(tài)為 \(s\) ，到目前位置推倒了 \(j\) 棵樹的答案

考慮直接將輪廓線上的點定義為 {沒推倒，向\(E\)推倒，向\(S\)推倒} 三種不僅無法很好描述狀態(tài)來轉移，復雜度也差強人意

觀察發(fā)現(xiàn)，對于輪廓線上的點轉移到下一狀態(tài)時，被推倒和因為其他樹推倒在它身上導致不能推倒是等價的.

換一種說法，輪廓線上的點對后面狀態(tài)的更新當且僅當取決于其在此刻能否被推倒，不妨用 \(0\) 表示可以被推倒 \(1\)表示不行

如圖所示，綠色的是當前的輪廓線，紅色的是要被更新的輪廓線，當前要把點 \(P_2\) 加到輪廓線中.

如果 \(mask(P_0) = 0\) 說明 \(P_0\) 能推倒但因為一些原因沒有推倒其右邊的點，根據題意，此時 \(P_0\) 必須要向下推倒

考慮 \(P_0\) 被向下推倒了之后，\(P_1\) 就不能向右推倒了，所以 \(P_1\) 如果要向下推倒選 \(S, E\) 都可以.

\(P_2\) 因為被卡住了不能動，所以選 \(S, E\) 也都可以，所以轉移的時候方案數的系數為 \(2 \times \max(2 \times [mask(P_1) = 0], 1)\)

如果 \(mask(P_0) = 1\) 且　\(maxk(P_1) = 0\)

此時 \(P_1\) 既可以向下推倒又可以向右推倒，向下的情況只需要保留當且輪廓線的狀態(tài)即可

考慮 \(P_1\) 要向右推倒，當且僅當 \(P_0\) 沒有向下推倒且 \(P_1\) 上的字母為 \(E\) , 所以轉移的時候方案數的系數為 \(2\)

如果都不能推倒，那么只需要保留當前輪廓線狀態(tài)并添加新的點 \(P_2\) 即可

考慮邊界的情況，對于所有右邊界和下邊界，推倒的樹的字母都可以選擇兩種

特別的，對于下邊界上的點，\(P_1\) 只能選擇向右推倒，對于最后狀態(tài)產生的未推倒的樹，都可以選取兩種顏色

所以只需要枚舉輪廓線和推倒的樹的個數，分類討論轉移

此題細節(jié)比較多，建議多算幾遍系數，復雜度是 \(O(\frac{W^2H}{2}\times2^W)\)

/*program by mangoyang*/ typedef long long ll; ll f[45][10][176][1<<7], Mod; inline void update(ll &x, ll y){ (x += y) %= Mod; } int BearDestroysDiv2::sumUp(int W, int H, int MOD){memset(f, 0, sizeof(f)); int all = W * H / 2 + 1, lim = (1 << W) - 1;f[0][W][0][lim] = 1, Mod = MOD;for(int i = 1; i <= H; i++){for(int j = 0; j <= all; j++)for(int s = 0; s <= lim; s++) f[i][0][j][s] = f[i-1][W][j][s];for(int r = 0; r < W; r++)for(int j = 0; j <= all; j++)for(int s = 0; s <= lim; s++){if(!((1 << r) & s)){ll s2 = (r == W - 1) ? 2 : 1, s1 = 1;if(r && !((1 << r - 1) & s) && i != H) s1 = 2; update(f[i][r+1][j+1][s|(1<<r)], f[i][r][j][s] * 2 * s2 * s1);}else{if(i < H) update(f[i][r+1][j][s^(1<<r)], f[i][r][j][s]);if(r && !((1 << r - 1) & s)){ll s2 = (i == H) ? 2 : 1;update(f[i][r+1][j+1][s|(1<<r)|(1<<r-1)], f[i][r][j][s] * 2 * s2);}else if(i == H) update(f[i][r+1][j][s^(1<<r)], f[i][r][j][s]);}} }ll ans = 0;for(int j = 1; j <= all; j++) for(int s = 0; s <= lim; s++) if(f[H][W][j][s]){ll res = 1;for(int i = 0; i < W; i++)if(!((1 << i) & s)) res *= 2;update(ans, f[H][W][j][s] * j * res);}return ans; }

轉載于:https://www.cnblogs.com/mangoyang/p/9362080.html

總結

以上是生活随笔為你收集整理的Topcoder Srm 671 Div2 1000 BearDestroysDiv2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。