TopCoder SRM 593 Div1 Medium MayTheBestPetWin

問題

動物がn匹いて、2チームに振り分けてリレーをする。
それぞれの動物は、自分の区間をA[i]秒以上B[i]秒以下のどれかの時間で走る。


二つのチームの走行時間の差の最大値が最小になるようなチーム分けにおける、
走行時間の差の最大値を求めよ。

制約条件

n≦50
A[i], B[i]≦10000

方針

片方のチームをSとする。
走行時間差が最大になるのは、Sのチーム全員がA[i]で走って残りのチームが全員B[i]で走った場合か、
Sのチーム全員がB[i]で走って残りのチームが全員A[i]で走った場合。


前者の場合Sの走行時間はΣ[i∈S]Aiで、このときの差の最大値は、
ΣBi - Σ[i∈S](Ai + Bi)


後者の場合
ΣAi - Σ[i∈S](Ai + Bi)


なので、Ai + Biの取りうる値を調べれば、
そのときの前者、後者の走行時間差が求められ、
そのmaxを取れば一つのチームわけにおける時間差の最大値が求まることになる。


Ai + Biの取りうる値すべてはDPで簡単にもとまる。

ソースコード

bool dp[1100000];

struct MayTheBestPetWin{
	int calc(vector <int> A, vector <int> B){
		int n = A.size();
		int ans = inf, a = 0, b = 0;
		
		dp[0] = 1;
		rep(i, n){
			a += A[i];
			b += B[i];
			for(int j = 1100000 - 1; j >= 0; j--) if(dp[j] && j + A[i] + B[i] < 1100000) dp[j + A[i] + B[i]] = 1;
		}
		
		rep(i, 1100000) if(dp[i]){
			ans = min(ans, max(abs(b - i), abs(a - i)));
		}
		return ans;
	}
};