給 N (≤100) 塊晶體，高度為正整數，總高度 < 2000。
將晶體分成兩堆，使兩堆高度相等且盡可能高。
輸出最大等高高度，若不可能輸出 "Sorry"。
dp[i][d]：前 i 塊晶體，兩塔高度差為 d 時，較矮塔的最大高度。
若不可達則為 -1。
初始 dp[0][0] = 0。
第 i 塊晶體高度 h，三種選擇：
dp[i][d] = max(dp[i][d], dp[i-1][d])dp[i][d+h] = max(dp[i][d+h], dp[i-1][d])h ≤ d：新差值 d-h，矮塔增高 h → dp[i][d-h] = max(dp[i][d-h], dp[i-1][d] + h)h-d，原矮塔變高塔，新矮塔高度 = 原高塔高度 = dp[i-1][d] + d → dp[i][h-d] = max(dp[i][h-d], dp[i-1][d] + d)僅依賴 i-1 層，使用兩個 1D 陣列交替：
int dp[2005], ndp[2005];
fill(dp, dp+2005, -1); dp[0] = 0;
for (int i=1; i<=n; ++i) {
copy(dp, dp+2005, ndp); // 不使用
for (int d=0; d<=2000; ++d) if (dp[d] != -1) {
int h = a[i];
// 放高塔
if (d+h <= 2000) ndp[d+h] = max(ndp[d+h], dp[d]);
// 放矮塔
if (h <= d) ndp[d-h] = max(ndp[d-h], dp[d] + h);
else ndp[h-d] = max(ndp[h-d], dp[d] + d);
}
swap(dp, ndp);
}
int ans = dp[0]; // 差值為 0 時的矮塔高度即為雙塔高度
cout << (ans > 0 ? ans : "Sorry") << "\n";
#includeusing namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin >> n, n > 0) { vector a(n+1); for (int i=1; i<=n; ++i) cin >> a[i]; const int MAXH = 2000; vector dp(MAXH+1, -1), ndp(MAXH+1, -1); dp[0] = 0; for (int i=1; i<=n; ++i) { ndp = dp; // 不使用 int h = a[i]; for (int d=0; d<=MAXH; ++d) if (dp[d] != -1) { // 放高塔 if (d + h <= MAXH) ndp[d+h] = max(ndp[d+h], dp[d]); // 放矮塔 if (h <= d) ndp[d-h] = max(ndp[d-h], dp[d] + h); else ndp[h-d] = max(ndp[h-d], dp[d] + d); } dp.swap(ndp); } if (dp[0] > 0) cout << dp[0] << "\n"; else cout << "Sorry\n"; } return 0; }
O(N × MAXH) = 100 × 2000 = 2×10⁵O(MAXH) = 2001 整數輸入: 4 11 11 11 11 4 1 11 111 1111 -1 輸出: 22 Sorry
解析：
Case 1：四塊 11，分兩堆各兩塊 → 22
Case 2：總高 1234，無法平分
