AtCoder Beginner Contest 032
C
しゃくとり法。バグりやすいからやりたくないんだよな・・・→1WA
Submission #959173 - AtCoder Beginner Contest 032 | AtCoder
無理やり通した。これだとなんか嫌なので、
きれいなコードになるように整えて再提出。
D
教育的な感じ。
n <= 30
全探索。 でたぶん大丈夫。→1回TLE
試しに全部入れてもWを超えないような最大の入力をやってみたら、
javaだと6秒くらいかかった。こういう場合はvの合計を出力するようにする。
ちゃんと気を付けてる? って言われているよう。
自分の撃墜コードももちろん思い浮かぶが、それはこの問題では問われていないみたい。
1 <= v_i <= 1000
vを全部足しても高々200 \times 1000 これにN=200の遷移がついても問題なさそう。
なので、
dp[i] := 価値合計iにおける容量合計の最小値
と置いてDP。
1 <= w_i <= 1000
同様に
dp[i] := 容量合計iにおける価値合計の最大値
と置いてDP。