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; }