HDU 5375 Gray Code：格雷碼動態規劃 / 貪心優化

題目大意

• 給定長度 `n` 的字符串，含 `0` `1` `?`（`?` 可替換為 0/1）。
• 對應二進制數轉格雷碼：`g[1]=b[1]`，`g[i]=b[i-1] XOR b[i]`。
• 每位 `g[i]=1` 獲得分數 `a[i]`，求最大總分。
• `n ≤ 2e5`，多測試用例。

DP 解法 O(n)

dp[i][0/1]：前 `i` 位，第 `i` 位二進制為 0/1 時的最大分數。
轉移：枚舉當前位可取值，依據前一位值計算格雷碼位得分。
初始：`i=1` 時 `g[1]=b[1]`。

貪心/規律法 O(n)（更簡潔）

觀察格雷碼：`g[i] = b[i-1] XOR b[i]`。
連續 `?` 段兩端為確定位 `x`、`y`（或邊界視為 0）。
設段長 `len`（含兩端確定位間的 `?` 數）。

• 若 `x == y`：
   `len` 奇數 → 全段貢獻和；
   `len` 偶數 → 全段和 - 最小值。
• 若 `x != y`：
   `len` 偶數 → 全段和；
   `len` 奇數 → 全段和 - 最小值。

掃描字符串，維護段內和與最小值，按規則累加答案。

完整代碼（貪心版）

#include 
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        string s; cin >> s;
        int n = s.size();
        vector a(n+1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        s = "0" + s; // 前導虛擬 0
        ll ans = 0;
        int segStart = 0; // 段起始確定位索引
        char last = '0';
        int segSum = 0, segMin = INT_MAX, qCnt = 0;
        for (int i = 1; i <= n; ++i) {
            if (s[i] != '?') {
                // 結算上一段
                if (qCnt > 0) {
                    if (last == s[i]) { // x == y
                        if (qCnt % 2 == 1) ans += segSum;
                        else ans += segSum - segMin;
                    } else { // x != y
                        if (qCnt % 2 == 0) ans += segSum;
                        else ans += segSum - segMin;
                    }
                } else if (last != s[i]) { // 相鄰確定位不同
                    ans += a[i];
                }
                // 重置
                last = s[i];
                segSum = 0; segMin = INT_MAX; qCnt = 0;
            } else {
                ++qCnt;
                segSum += a[i];
                segMin = min(segMin, a[i]);
            }
        }
        cout << "Case #" << cs << ": " << ans << "\n";
    }
    return 0;
}

複雜度

• 單次掃描 O(n)，常數極小。
• DP 版同樣 O(n) 但狀態轉移稍繁瑣。