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