UVa 10690 : Expression Again
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; }