はまやんはまやんはまやん

hamayanhamayan's blog

世界史のレポート [yukicoder No.555]

https://yukicoder.me/submissions/196775

解説放送

未定

解説

https://yukicoder.me/submissions/196775

dp[i] := i個のAを作るための最小コスト
全ての遷移を全探索で行っていく。
dp[i]からの遷移先は、コピーをして、
dp[i + i] = dp[i] + C + V
dp[i + i * 2] = dp[i] + C + V * 2
dp[i + i * 3] = dp[i] + C + V * 3

とする。

これを愚直にやれば間に合う。
間に合わない気もするが、実は計算量はO(NlogN)
これはエラトステネスの篩と同じ原理でO(NlogN)である

#define INF INT_MAX/2
int N, C, V;
int dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> C >> V;

    rep(i, 0, 101010) dp[i] = INF;
    dp[1] = 0;
    rep(i, 1, N) {
        int c = dp[i] + C + V;
        for (int x = i * 2; x < 101010; x += i) dp[x] = min(dp[x], c), c += V;
    }

    int ans = INF;
    rep(i, N, 101010) ans = min(ans, dp[i]);
    cout << ans << endl;
}