読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 10690 : Expression Again

UVa演習 動的計画法

UVa演習 : 2014/6/10 (火) 問8

問題リンク : http://uva.onlinejudge.org/external/106/10690.html

問題概要:
N+M個の整数(-50以上50以下)が与えられる
(x1+x2+...+xN)*(y1+y2+...+yM)の最大値と最小値を求めよ

解法:
動的計画法
dp[i個の整数をつかった][その時の和] := 作れるか
10^9ちょいだけど6秒あるから十分間に合った

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int IINF = INT_MAX, coef = 2500;

bool dp[51][5010];
int v[110];

int main(){
  int N,M;
  while( cin >> N >> M ){
    int sum = 0;
    rep(i,(N+M)) {
      cin >> v[i];
      sum += v[i];
    }
    rep(i,min(N,M)+1) rep(j,5010) dp[i][j] = false;
    dp[0][coef] = true; 
    rep(i,(N+M)){
      for(int j=min(M,N)-1;j>=0;j--){
        rep(k,5010){
          if( !dp[j][k] ) continue;
          int cost = k + v[i];
          if( !( 0 <= cost && cost < 5010 ) ) continue;
          dp[j+1][cost] = true;
        }
      }
    }

    int maxi = -IINF, mini = IINF;

    rep(i,5010){
      if( !dp[min(N,M)][i] ) continue;
      maxi = max(maxi,( i - coef ) * ( sum - ( i - coef ) ));
      mini = min(mini,( i - coef ) * ( sum - ( i - coef ) ));
    }

    cout << maxi << ' ' << mini << endl;

  }
  return 0;
}