ZOJ 3802：Easy 2048 Again - 狀態壓縮 DP

問題描述

模擬 2048 遊戲的一維版：有一個隊列，每次可從給定序列中取一個數字加入隊列尾部。隊列中相鄰相同數字可合併（值翻倍），合併後可能繼續連鎖合併。求操作 n 步後隊列中數字之和的最大值。

關鍵觀察：隊列單調性

若隊列中出現 a, b 且 a < b，則 a 左側的數永遠無法與 b 發生連鎖合併（因合併只會讓數字變大）。因此隊列始終保持非嚴格遞減，且最大值不斷增長。由於數值上限有限，隊列長度最多約 12-13，可用狀態壓縮。

狀態表示

• 隊列中每個數字為 2 的冪次，用位掩碼表示：第 i 位為 1 表示存在 2ⁱ。
• 狀態空間 2¹³ = 8192，極小。
• 滾動數組 dp[2][8192] 優化空間。

轉移邏輯

對於當前狀態 S 和新數字 x：

• 若隊列為空或最小元素 > x：直接加入尾部，新狀態 S | (1<<x)。
• 若最小元素 == x：觸發合併，循環合併直到無法合併，更新狀態與得分。
• 若最小元素 < x：無法合併，直接加入尾部（但實際上因單調性不會發生）。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MX = 505, MY = (1<<13) + 5;
int n, g[MX], dp[2][MY];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &g[i]);
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            int cur = i & 1, pre = cur ^ 1;
            memset(dp[cur], -1, sizeof(dp[cur]));
            for (int S = 0; S < MY; ++S) if (dp[pre][S] != -1) {
                // 不取
                dp[cur][S] = max(dp[cur][S], dp[pre][S]);
                // 取 g[i]
                int temp = 0;
                if (S) for (int k = 0; k <= 12; ++k) if (S & (1< g[i]) { // 無法合併或空隊列
                    dp[cur][S | (1<