10690 Expression Again

題目連結

題目描述

你會得到一個代數表達式，形式為：

(x1 + x2 + x3 + ... + xn) * (y1 + y2 + ... + ym)

以及總共 (n + m) 個整數

你需要使用這些給定的整數來找出這個表達式的最大值與最小值
例如，若給你：

(x1 + x2) * (y1 + y2)

以及數字：1、2、3、4，那麼最大值為：

(1 + 4) * (2 + 3) = 25

最小值為：

(4 + 3) * (2 + 1) = 21

輸入說明

每筆輸入資料以兩個正整數 N 與 M 開始（N, M < 51）
接下來的一行包含 (N + M) 個整數，範圍介於 -50 到 50 之間
輸入以檔案結尾（EOF）作為結束。最多會有 110 組測資

輸出說明

對於每一組測資，請輸出一行：最大值 與 最小值（以空格分隔）

解題思路

程式碼

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
    int x, y;
    while (cin >> x >> y) {
        vector<int> v(x+y);
        int sum = 0;
        for (auto &i : v) {
            cin >> i;
            sum += (i += 50);
        }

        if (x > y) swap(x, y);

        bitset<100*100+10> dp[x+1]; dp[0][0] = 1;
        for (int i = 0; i < x+y; i++) for (int j = x; j >= 1; j--) dp[j] |= (dp[j-1] << v[i]);

        int mx = -1e9, mn = 1e9;
        for (int i = 0; i <= sum; i++) if (dp[x][i]) {
            int k = (i-x*50) * (sum-i-y*50);
            mx = max(mx, k);
            mn = min(mn, k);
        }

        cout << mx << ' ' << mn << '\n';
    }
}