POJ 1837 Balance：天平平衡 DP（狀態壓縮枚舉）

問題描述

天平兩臂長 15，有 C (≤20) 個掛鉤，位置為 -15..15 非零整數（負左正右）。有 G (≤20) 個砝碼，重量 1..25 互不相同。必須用完所有砝碼，每個砝碼掛在任一掛鉤。求平衡方案數（力矩和為 0）。保證至少一解。

狀態定義：力矩偏移 DP

力矩 = 重量 × 位置。最大力矩絕對值 20 * 25 * 15 = 7500。定義 dp[i][m]：前 i 個砝碼放置後，力矩和為 m - 7500 的方案數。偏移量 SHIFT = 7500 使下標非負。狀態數 21 * 15001 ≈ 3.1e5。

轉移方程

dp[i][m] = Σ_{hook} dp[i-1][m - w[i] * hook_pos]

初始 dp[0][SHIFT] = 1（無砝碼力矩 0）。答案 dp[G][SHIFT]。

優化細節

• 滾動數組：只需 dp[2][15001]，空間減半。
• 砝碼順序任意，但需用完所有。
• 掛鉤位置可預存數組。

參考代碼 (C++)

#include 
using namespace std;
const int SHIFT = 7500;
const int MAXM = 15001;
long long dp[2][MAXM];
int hook[25], w[25];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int C, G;
    while (cin >> C >> G) {
        for (int i = 0; i < C; ++i) cin >> hook[i];
        for (int i = 1; i <= G; ++i) cin >> w[i];
        memset(dp, 0, sizeof(dp));
        dp[0][SHIFT] = 1;
        for (int i = 1; i <= G; ++i) {
            int cur = i & 1, pre = cur ^ 1;
            memset(dp[cur], 0, sizeof(dp[cur]));
            for (int m = 0; m < MAXM; ++m) if (dp[pre][m]) {
                for (int h = 0; h < C; ++h) {
                    int nm = m + w[i] * hook[h];
                    if (nm >= 0 && nm < MAXM) dp[cur][nm] += dp[pre][m];
                }
            }
        }
        cout << dp[G & 1][SHIFT] << '\n';
    }
    return 0;
}

複雜度

時間 O(G * MAXM * C) ≈ 20 * 15001 * 20 = 6e6，空間 O(MAXM)，輕鬆通過。

核心思想

• 將物理平衡條件（力矩和為 0）轉化為整數 DP 狀態。
• 偏移量技巧處理負數下標。
• 「枚舉上一狀態 + 選擇動作 → 更新新狀態」是典型 DP 範式。

總結

• 天平問題本質是子集和變體：每個物品有多種「重量」（力矩貢獻），求和為 0 的方案數。
• 數據範圍小，直接 DP 即可，無需優化。
• 注意力矩上界計算：max_weight * max_arm * G。