No.458 異なる素数の和

Quiz

https://yukicoder.me/problems/no/458

Submit

https://yukicoder.me/submissions/339334

解法

  • dp[i] : i を異なる素数の和で表した時の最大の和の回数
  • 答えはdp[N]

考察1 dp[i]をより小さいdpで埋めていく

f:id:peroon:20190417123334j:plain

  • よくある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){
  }
}
  • この形
  • しかしどう埋めていけばいいか不明

f:id:peroon:20190417123357j:plain

考察3 素数を滑らせながらdp[i]を埋めていく

for(int p : prime_list){
  FOR(i, 0, N+1){
  }
}
  • この形
  • しかし画像のように、順方向にiを動かしてはいけない。同じ素数を複数回使ってしまうから。

f:id:peroon:20190417123500j:plain

  • なので、正しくは下記のループで埋めていけばいい
for(int p : prime_list){
  for(int i=N; i>=0; i--){
  }
}