HDOJ 5375 Gray Code DP：狀態轉移詳解

DP 狀態定義

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

轉移方程

格雷碼 `g[i] = b[i-1] XOR b[i]`（`b[0]` 視為 0）。
當前位 `b[i]` 可取值受 `s[i]` 限制（`0`/`1`/?）。

• 若 `s[i] == '0'`：只能 `b[i]=0`。
   `dp[i][0] = max(dp[i-1][0] + 0, dp[i-1][1] + a[i])`（`g[i]=0^0=0` 得 0 分，`g[i]=1^0=1` 得 `a[i]` 分）。
• 若 `s[i] == '1'`：只能 `b[i]=1`。
   `dp[i][1] = max(dp[i-1][1] + 0, dp[i-1][0] + a[i])`。
• 若 `s[i] == '?'`：兩種均可。
   `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])`。

完整代碼

#include 
using namespace std;
const int MAXN = 200005;
int dp[MAXN][2], a[MAXN];
char s[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    for (int cs = 1; cs <= T; ++cs) {
        cin >> (s+1);
        int n = strlen(s+1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        memset(dp, 0, sizeof(dp));
        // i=1 初始化
        if (s[1] == '0') dp[1][0] = 0;
        else if (s[1] == '1') dp[1][1] = a[1];
        else { dp[1][0] = 0; dp[1][1] = a[1]; }
        for (int i = 2; i <= n; ++i) {
            if (s[i] == '0') {
                dp[i][0] = max(dp[i-1][0], dp[i-1][1] + a[i]);
            } else if (s[i] == '1') {
                dp[i][1] = max(dp[i-1][1], dp[i-1][0] + a[i]);
            } else { // '?'
                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]);
            }
        }
        int ans = max(dp[n][0], dp[n][1]);
        cout << "Case #" << cs << ": " << ans << "\n";
    }
    return 0;
}

複雜度

• 時間 O(n)，空間 O(n)（可滾動至 O(1)）。