yukicoder No.385 カップ麺生活

問題

問題概要

カップ麺を買う。買っていく途中で所持金が素数になるとはじめの所持金に戻ることができる。ただし、1つの素数につき、1度だけしか戻ることはできない。最大でいくつのカップ麺を買うことができるかを求める。

解法

まず、所持金以下の数字の中で、素数を求めておく。エラトステネスを用いて、この処理を行った。次に、カップ麺を買っていく時に、その値段にその値段に達するまあでに、最も多くカップ麺を買う時の個数をdpで求める。
dp[残りの所持金がi] = (残りの所持金iの時に買えるカップ麺の最大数)として求めていけばいい。
どの所持金の時の元の所持金に戻るかは、所持金m以下の時の素数となる所持金すべてにおいて、戻ればいい。元の所持金に戻れれるなら、カップ麺を変える個数は増えるはず。最後に最も安いカップ麺を変えるだけ買えばいい。

ミス

なし

コード

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int dp[10010];
bool isprime[10010];//trueならiは素数

//エラトステネス
void eratos(int m){
    for (int i = 0; i <= m; ++i) isprime[i] = true;
    isprime[0] = isprime[1] = false;
    //iを残してiの倍数を消していく
    for (int i = 2; i <= m; ++i){
        if(isprime[i]){
            for (int j = 2 * i; j <= m; j += i){
                isprime[j] = false;
            }
        }
    }
    return;
}

int main(void){
    int m, n; cin >> m >> n;
    eratos(m);
    vector<int> c(n);
    rep(i, n) cin >> c[i];
    sort(c.begin(), c.end());
    memset(dp, -1, sizeof(dp));

    dp[m] = 0;
    for (int i = m; i >= 0; --i){//所持金の残り
        for (int j = 0; j < n; ++j){//すべてのカップ麺を調べる
            if(i - c[j] >= 0 && dp[i] >= 0){
                dp[i - c[j]] = max(dp[i - c[j]], dp[i] + 1);
            }
        }
    }

    int ans = 0;
    //残りの所持金が素数の時
    for (int i = 0; i <= m; ++i){
        if(dp[i] != -1 && isprime[i] == true) ans += dp[i];
    }
    //残りの所持金が素数の時をすべて廻ったあとは一番安いカップ麺を買えばいい
    while(m > 0){
        if(m - c[0] >= 0) ans++;
        m -= c[0];
    }
    printf("%d\n", ans);
}