UVA - 10690 Expression Again

Description

Problem C

Expression Again

Input: standard input
Output: standard output

TimeLimit: 6 seconds

You are given an algebraic expression of the form(x1+x2+x3+.....+xn)*(y1+y2+.........+ym) and (n+m) integers. Youhave to find the maximum and minimum value of the expression using the givenintegers. For example if you are given (x1+x2)*(y1+y2) and you are given1, 2, 3 and 4. Then maximum value is (1+4)*(2+3) = 25whereas 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 therange of -50 to 50. Input is terminated by end of file. Therewill be atmost 110 testcases.

Output

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

SampleInput Outputfor Sample Input

2 2

1 2 3 4

3 1

1 2 3 4

2 2

2 2 2 2

題意：給你n+m個數，讓你分成n個和m個，求它們的和的積的最大和最小

思路: 動態規劃，設dp[i][j]表示用i個組成j的可能性，最後在從所有的可能裡求解

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 110;

int dp[maxn][maxn*maxn];
int n, m;

int main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		vector ve(n+m+1);
		int sum = 0;
		for (int i = 1; i <= n+m; i++) {
			scanf("%d", &ve[i]);
			sum += ve[i];
			ve[i] += 50;
		}
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for (int i = 1; i <= n+m; i++) {
			for (int j = min(i, n); j >= 1; j--) //反著來消除後效性
				for (int k = 0; k <= 10000; k++)
					if (dp[j-1][k])
						dp[j][k+ve[i]] = 1;
		}
		int Max = -5000;
		int Min = 5000;
		for (int i = 0; i <= 10000; i++)
			if (dp[n][i]) {
				int tmp = i - 50 * n;
				Max = max(Max, tmp*(sum-tmp));
				Min = min(Min, tmp*(sum-tmp));
			}
		printf("%d %d\n", Max, Min);
	}
	return 0;
}