Quiz
https://yukicoder.me/problems/no/458
Submit
https://yukicoder.me/submissions/339334
解法
- dp[i] : i を異なる素数の和で表した時の最大の和の回数
- 答えはdp[N]
考察1 dp[i]をより小さいdpで埋めていく
- よくあるDP
- しかし今回はダメ
- dp[7] != dp[2] + dp[5] であるため
- dp[2] = 1 (素数2のみ)
- dp[5] = 2 (素数2と3)
- dp[7] = 2 (素数2と5)
- dp[7] = 3ではない (素数が2, 2, 3となるため)
考察2 dp[i]をiが小さい方から埋めていく (素数を滑らす)
FOR(i, 0, N+1){ for(int p : prime_list){ } }
- この形
- しかしどう埋めていけばいいか不明
考察3 素数を滑らせながらdp[i]を埋めていく
for(int p : prime_list){ FOR(i, 0, N+1){ } }
- この形
- しかし画像のように、順方向にiを動かしてはいけない。同じ素数を複数回使ってしまうから。
- なので、正しくは下記のループで埋めていけばいい
for(int p : prime_list){ for(int i=N; i>=0; i--){ } }