HDU 5375 Gray Code：動態規劃求最大得分

題目大意

給定長度 n 的二進制串（含 0, 1, ?），? 可替換為 0 或 1。轉換為格雷碼後，第 i 位為 1 可得 a_i 分。求最大得分。n ≤ 200000。

格雷碼轉換公式

G[0] = B[0]，G[i] = B[i] XOR B[i-1]。即當二進制相鄰兩位不同時，格雷碼該位為 1。

動態規劃

• dp[i][0]：前 i 位，第 i 位二進制為 0 的最大得分。
• dp[i][1]：前 i 位，第 i 位二進制為 1 的最大得分。

轉移：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + a[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + a[i]);

答案為 max(dp[n-1][0], dp[n-1][1])。

參考代碼 (C++)

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

const int MOD = 1e9+7;
const int MAXN = 200005;
char str[MAXN];
int a[MAXN], dp[MAXN][2];

int main() {
    int T; scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        scanf("%s", str);
        int n = strlen(str);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        dp[0][0] = dp[0][1] = 0;
        if (str[0] != '1') dp[0][0] = 0;
        if (str[0] != '0') dp[0][1] = 0;
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i][1] = -1e9;
            if (str[i] != '1') {
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + a[i]);
            }
            if (str[i] != '0') {
                dp[i][1] = max(dp[i-1][1], dp[i-1][0] + a[i]);
            }
        }
        int ans = max(dp[n-1][0], dp[n-1][1]);
        printf("Case #%d: %d\n", t, ans);
    }
    return 0;
}