您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1717：Dominoes——DP 背包變體求最小翻轉次數

編輯：關於C++

題目描述

n 張多米諾骨牌，每張上下兩半分別有點數 aᵢ, bᵢ。初始上半和為 S₁，下半和為 S₂，差值 gap = |S₁ - S₂|。翻轉一張牌交換其上下值，改變 gap。求使 gap 最小所需的最少翻轉次數。

轉化為子集和問題

設 cᵢ = aᵢ - bᵢ。翻轉第 i 張牌使總差值變化 2·cᵢ。目標：選擇若干 cᵢ 使 |Σ 2cᵢ - gap| 最小，等價於在 {2cᵢ} 中選子集和最接近 gap。

DP 狀態

dp[j]：差值偏移 j 可達的最少翻轉數。偏移量範圍 [-12000, 12000]（每張最大差 6，n≤1000）。用偏移 12000 映射到非負索引。

滾動數組優化

const int OFFSET = 12000, MAXD = 24001;
int dp[MAXD], ndp[MAXD];
fill(dp, dp+MAXD, INF); dp[OFFSET] = 0;
for (int i = 1; i <= n; ++i) {
    int diff = 2 * (a[i] - b[i]);
    copy(dp, dp+MAXD, ndp);
    if (diff > 0)
        for (int j = diff; j < MAXD; ++j)
            ndp[j] = min(ndp[j], dp[j-diff] + 1);
    else
        for (int j = 0; j+diff < MAXD; ++j)
            ndp[j] = min(ndp[j], dp[j-diff] + 1);
    dp.swap(ndp);
}
int ans = INF;
for (int d = 0; d <= OFFSET; ++d)
    ans = min(ans, min(dp[OFFSET+d], dp[OFFSET-d]));
printf("%d\n", ans);