問題概要
今日はハロウィンなので、太郎君は近所の家におかしをもらいに行くことにしました。
近所には、太郎君の家以外に $N$軒の家があります。
それぞれの$i$家に行くとおかしを$Vi$個もらえるのですが、
近所のこどもたちに平等におかしを配るため、
すでにおかしを$Ti$個以上持っていると、おかしを一つももらえないことになっています。
太郎君は、最初におかしを一つも持っていないこととし、近所の家を周るのは好きな順番で周ることができるとき、
太郎君がもらえるおかしの最大の個数を求めてください。
同じ家には1回しか回れないとします。
$N\leqq10^4$、$V[i],T[i]\leqq10^4$
解法
順序が大事で、bitdpはできないので順序を自分で考える。 $x$番目と$y$番目で、どちらが先に訪れるのがうれしいかを考える。 $x$番目に先に訪れることで$y$番目を先に訪れた時よりも確実に良い結果を残すとき、 片側ではキャンディーを獲得できて片側では獲得できない状況が存在する。 つまり獲得について$(y) or (x ->y)$となる場合の比較基準を知りたい。
現在のキャンディー所持数を$K$とすると
$K+v[x]<t[y], K+v[y]≧t[x]$、と表現できる。
$K$について、$t[x]-v[y]≦K<t[y]-v[x]$、
はさんでいる式について整理すれば
$t[x]+v[x]<t[y]+v[y]$のとき、$x$に先に訪れるのが最適といことになる。
したがって$v+t$が小さい順番に訪問していけばよく、これを$dp$で回していけばよい。
具体的にはある値Vについて、今までの情報から作成可能かつ$t[i]$未満ならば$V+v[i]$も作成可能であるとすればよい。
$dp[$ 現在作成可能なキャンディー保持数 $]:=$ 作成可能/作成不可能
snukeさん
”“”
家$i$を使うときは「今の値が$Ti$以上なら$Vi$もらえる」ですが、
適当な大きい数$INF$を使ってこれを言い換えて
「値を$INF-Ti$増やしてから、$INF-Ti-Vi$減らす。
ただし、途中で値が$INF$を超えては行けない」ということにする。
これを折れ線で表してながめる。
折れ線を後ろからくっつけていくことにしてみると、
$INF-Ti-Vi$が小さい順にくっつけていくのが良さそうなことが分かると思います。
“””
賢すぎ。
計算量:$O(NT[i])$
ソース
#include <bits/stdc++.h> using namespace std; using VS = vector<string>; using LL = long long; using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; using PLL = pair<LL, LL>; #define ALL(a) begin((a)),end((a)) #define SORT(c) sort(ALL((c))) #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++) #define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--) LL N; LL ans = 0LL; int main() { cin.tie(0); ios_base::sync_with_stdio(false); cin >> N; vector<PII>a; VI v(N), t(N); FOR(i, 0, N) { cin >> v[i] >> t[i]; a.push_back(PII(v[i] + t[i], i)); } SORT(a); VI dp(20001, 0); dp[0] = 1; FOR(i, 0, N) { int id = a[i].second; FORR(h, t[id] - 1, 0 - 1) { dp[h + v[id]] |= dp[h]; } } FOR(i, 0, 20001) { if (dp[i]) { ans = i; } } cout << ans << "\n"; return 0; }