Codeforces 148E Porcelain：預處理 + 多重背包

題目大意

• `n` 層架子（`n ≤ 100`），每層若干物品（值 1..100），只能從兩端取。
• 共取 `m` 件（`m ≤ 10000`），求最大總價值。

預處理：每層前綴和 + 兩端取值最大值

對每層長度 `len`，計算前綴和 `pre[i]`。
取 `k` 件（`0 ≤ k ≤ min(len, m)`）的最大值：
`best[k] = max_{0≤i≤k} (pre[i] + pre[len] - pre[len - (k-i)])`。
即左取 `i`，右取 `k-i`。

多重背包 DP

dp[j]：取 `j` 件的最大價值。
對每層，倒序更新：
`for j = m..1: for k = 1..min(j, len): dp[j] = max(dp[j], dp[j-k] + best[k])`

完整代碼

#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector dp(m+1, 0);
    for (int shelf = 0; shelf < n; ++shelf) {
        int len; cin >> len;
        vector a(len+1), pre(len+1);
        for (int i = 1; i <= len; ++i) {
            cin >> a[i];
            pre[i] = pre[i-1] + a[i];
        }
        vector best(min(len, m)+1, 0);
        for (int k = 0; k <= min(len, m); ++k) {
            for (int i = 0; i <= k; ++i)
                best[k] = max(best[k], pre[i] + pre[len] - pre[len - (k-i)]);
        }
        for (int j = m; j >= 1; --j)
            for (int k = 1; k <= min(j, (int)best.size()-1); ++k)
                dp[j] = max(dp[j], dp[j-k] + best[k]);
    }
    cout << dp[m] << "\n";
    return 0;
}

複雜度

• 預處理：`O(n * len²)`，`len ≤ 100`，`n ≤ 100` → 1e6。
• 背包：`O(n * m * len)` → `100 * 10000 * 100 = 1e8` 邊界較緊，實際 `len` 平均較小可通過；可優化為分組背包單調隊列或二進制拆分，但本題數據通常允許三重循環通過。