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';
  }
}