Resale [AtCoder Beginner Contest 125 B]

https://atcoder.jp/contests/abc125/tasks/abc125_b

解説

今回の問題は解法が2つあるので、どちらも紹介する。
解法2の方が計算量が軽くておすすめだが、
解法1の全探索もやり方としては必ず覚えておく必要がある。

解法1 : 全探索

https://atcoder.jp/contests/abc125/submissions/5169297

N≦20なので、各宝石を取る取らないを全探索できる。
各状態についてX,Yを計算して、X-Yの最大値を答えると答え。
状態がO(2^N)あり、X,Yの計算にO(N)かかるので、全体O(2^N*N)で間に合う。

int N, V[20], C[20];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> V[i];
	rep(i, 0, N) cin >> C[i];
 
	int ans = 0;
	rep(msk, 0, 1 << N) {
		int X = 0, Y = 0;
		rep(i, 0, N) if (msk & (1 << i)) {
			X += V[i];
			Y += C[i];
		}
		chmax(ans, X - Y);
	}
	cout << ans << endl;
}

解法2 : 貪欲法

https://atcoder.jp/contests/abc125/submissions/5169289

X-Yの最大値を求めるが、1,2,3番目の宝石を選んだとすると、

X-Y
=(V1+V2+V3)-(C1+C2+C3)
=(V1-C1)+(V2-C2)+(V3-C3)

このようになるので、各宝石についてV[i]-C[i]を取っていくことに言い換えられる。
ここから、V[i]-C[i]が正であれば取ったほうがX-Yは大きくなるので、正であるものを貪欲に全て取ると答え。
O(N)

int N, V[20], C[20];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> V[i];
	rep(i, 0, N) cin >> C[i];
 
	int ans = 0;
	rep(i, 0, N) if (0 < V[i] - C[i]) ans += V[i] - C[i];
	cout << ans << endl;
}