Problem C

Expression Again

Input: standard input
Output: standard output

Time Limit: 6 seconds

You are given an algebraic expression of the form (x1+x2+x3+.....+xn)*(y1+y2+.........+ym) and (n+m) integers. You have to find the maximum and minimum value of the expression using the given integers. For example if you are given (x1+x2)*(y1+y2) and you are given 1, 2, 3 and 4. Then maximum value is (1+4)*(2+3) = 25 whereas minimum value is (4+3)*(2+1) = 21.

Input

Each input set starts with two positive integers N, M (less than 51). Next line follows (N+M) integers which are in the range of -50 to 50. Input is terminated by end of file. There will be atmost 110 testcases.

Output

Output is one line for each case, maximum value followed by minimum value.

Sample Input                           Output for Sample Input

2 2

1 2 3 4

3 1

1 2 3 4

2 2

2 2 2 2

25 21

24 9

16 16

Problem setter: Md Kamruzzaman, Member of Elite Problemsetters' Panel

Special Thanks: Monirul Hasan, Md. Sajjad Hossain

題目描述：

把 n+m 個整數分成一邊 n 個 另一邊 m 個，分別加總起來，相乘的最大值為何？最小值為何？

題目解法：

只求其中一邊即可，而另外一邊必然是 n+m 個整數的總和扣掉這一邊。
只要知道其中一邊的所有可能的結果，窮舉所有可能相乘情況找最大最小值。

由於題目有負數，因此在 dp 的時候，必須考慮會有負的背包問題，因此打算將陣列位移方便處理負數。

而一般處理正數背包是由後往前更新，負數就是由前往後更新。

而逐次擴大 dp 更新範圍，來加快速度。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char dp[10005][51];
int main() {
    int n, m, A[105];
    int i, j, k;
    while(scanf("%d %d", &n, &m) == 2) {
        int N = n+m, sum = 0;
        memset(dp, 0, sizeof(dp));
        for(i = 0; i < N; i++) {
            scanf("%d", &A[i]);
            sum += A[i];
        }
        dp[0+5000][0] = 1;
        if(n > m)   swap(n, m);
        int l = 5000, r = 5000;
        for(i = 0; i < N; i++) {
            if(A[i] >= 0) {
                int cut = min(i, n), nr = r;
                for(j = r; j >= l; j--) {
                    for(k = 0; k <= cut; k++)
                        if(dp[j][k]) {
                            dp[j+A[i]][k+1] = 1;
                            nr = max(nr, j+A[i]);
                        }
                }
                r = nr;
            } else {
                int cut = min(i, n), nl = l;
                for(j = l; j <= r; j++) {
                    for(k = 0; k <= cut; k++) {
                        if(dp[j][k]) {
                            dp[j+A[i]][k+1] = 1;
                            nl = min(nl, j+A[i]);
                        }
                    }
                }
                l = nl;
            }
        }
        int mn = 0xfffffff, mx = -0xfffffff;
        for(i = l; i <= r; i++) {
            if(dp[i][n]) {
                mn = min(mn, (i-5000)*(sum-i+5000));
                mx = max(mx, (i-5000)*(sum-i+5000));
            }
        }
        printf("%d %d\n", mx, mn);
    }
    return 0;
}