超能力者Aと株価予測 [yukicoder No.664]

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

解法

https://yukicoder.me/submissions/243148

dpで解いていこう。
「dp[m][n] := n日目まで終了してm回売買を済ませた場合の資金の最大値」
dp[0][0] = K
dp[m][n] = max( max{i=0..n-1} (dp[m-1][i] % A[i] + floor(dp[m-1][i] / A[i]) * A[n]) , dp[m][n-1] )
これで更新すれば答えになる。
最適行動について考えてみると「i日目に買ってj日目に売るとすると、i日目に買えるだけ買ってj日目に全部売る」というのを繰り返すのが良い。
これをDPでやっていく。
（最適行動であるか未証明であるので、チャレンジされるかもしれない）

int N, M, K, A[401];
ll dp[30][401];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    N++;
    rep(i, 0, N) cin >> A[i];

    dp[0][0] = K;
    rep(m, 1, M + 1) {
        rep(n, 1, N) chmax(dp[m - 1][n], dp[m - 1][n - 1]);
        rep(n, 0, N) {
            rep(i, 0, n) {
                ll d = dp[m - 1][i] / A[i];
                ll c = dp[m - 1][i] % A[i] + d * A[n];
                chmax(dp[m][n], c);
            }
        }
    }

    ll ans = 0;
    rep(m, 0, M + 1) rep(n, 0, N) chmax(ans, dp[m][n]);
    cout << ans << endl;
}