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