POJ 1837 Balance：天平平衡方案數 (動態規劃背包)

問題描述

有一個長度為 15 的天平，左右各有若干掛鉤（位置 -15..-1 和 1..15，0 為中心）。給定 C 個掛鉤位置（互不相同、已排序）和 G 個重量互不相同的鉤碼（1..25）。必須將所有鉤碼掛在掛鉤上（每鉤最多一個鉤碼），使天平平衡（力矩和為 0）。求平衡的方案數。保證至少有一解。

輸入：C G，掛鉤位置陣列，鉤碼重量陣列。2 ≤ C,G ≤ 20。

輸出：平衡方案數 M。

範例

Input:
2 4
-2 3
3 4 5 8
Output:
2

解題思路：動態規劃

定義 平衡度 j = 右側力矩和 - 左側力矩和。平衡即 j = 0。

狀態：dp[i][j] 表示掛前 i 個鉤碼後，平衡度為 j 的方案數。

由於最大力矩：20 個鉤碼 × 25 重量 × 15 距離 = 7500，平衡度範圍 [-7500, 7500]。為避免負下標，引入偏移量 OFFSET = 7500，實際陣列下標 j + OFFSET。

初始：dp[0][OFFSET] = 1（掛 0 個鉤碼，平衡度 0 有 1 種方案）。

轉移：對第 i 個鉤碼（重量 w[i]），枚舉所有可能的平衡度 j 和所有掛鉤位置 pos[k]：

new_j = j + w[i] * pos[k]
dp[i][new_j] += dp[i-1][j]

最終答案：dp[G][OFFSET]。

關鍵代碼片段 (C++)

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

const int MAXG = 20;
const int OFFSET = 7500;
const int MAXJ = 15000;

int dp[MAXG+1][MAXJ+1];
int hook[MAXG+1], weight[MAXG+1];

int main() {
    int C, G;
    while (scanf("%d%d", &C, &G) == 2) {
        for (int i = 1; i <= C; ++i) scanf("%d", &hook[i]);
        for (int i = 1; i <= G; ++i) scanf("%d", &weight[i]);
        memset(dp, 0, sizeof(dp));
        dp[0][OFFSET] = 1;
        for (int i = 1; i <= G; ++i) {
            for (int j = 0; j <= MAXJ; ++j) {
                if (dp[i-1][j]) {
                    for (int k = 1; k <= C; ++k) {
                        int nj = j + weight[i] * hook[k];
                        if (nj >= 0 && nj <= MAXJ)
                            dp[i][nj] += dp[i-1][j];
                    }
                }
            }
        }
        printf("%d\n", dp[G][OFFSET]);
    }
    return 0;
}

複雜度分析

• 狀態數：G × 15001 ≤ 20 × 15001 ≈ 3×10^5。
• 轉移：每狀態枚舉 C ≤ 20 個掛鉤，總操作數 ≈ 6×10^6，極快。
• 空間：21 × 15001 × 4 bytes ≈ 1.2 MB。

總結

POJ 1837 是典型的「計數型背包 DP」。將物理平衡條件轉化為力矩差（平衡度），引入偏移量處理負數下標，逐個鉤碼更新 DP 表。關鍵在於識別出「平衡度」作為狀態，並正確處理正負力矩的抵消。題目保證有解，無需處理無解情況。