式がいかめしくて戸惑うけど、DP 自体は比較的単純

問題へのリンク

問題概要

$N$ 個の値 $P_{1}, P_{2}, \dots, P_{N}$ が与えられる。

これらの中から順序を保っていくつか選ぶ。選び方のスコアは、 $k$ 個の整数 $Q_{1}, Q_{2}, \dots, Q_{k}$ を選んだとしたとき、

で与えられる。このスコアの最大値を求めよ。

制約

$1 \le N, P_{i} \le 5000$

考えたこと

とにかく式がいかめしい。しかしサンプルを見ると分かってくる。たとえば $Q = (1200, 600, 1000)$ だった場合には、計算式は

$\displaystyle \frac{0.9^{2} \times 1200 + 0.9 \times 600 + 1000}{0.9^{2} + 0.9 + 1} - \frac{1200}{\sqrt{k}}$

となる。 $k$ を固定した場合には、

$0.9^{2} \times Q_{1} + 0.9 \times Q_{2} + Q_{3}$

の部分のみ最大化すればよいのだ (それ以外は定数)。よって、次のような DP を組んだ (ここから 0-indexed にする)。

dp[i][j] ← $P_{0}, P_{1}, \dots, P_{i-1}$ の中から $j$ 個選んで、それらに前から $0.9^{j-1}, 0.9^{j-2}, \dots, 1$ をかけて、総和をとった値の最大値

DP 更新式は次のように書ける。

chmax(dp[i+1][j], dp[i][j]);
chmax(dp[i+1][j+1], dp[i][j] * 0.9 + P[i]);

以上の解法の計算量は $O(N^{2})$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<double> P(N), fac(N+1, 0);
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
        fac[i+1] = fac[i] * 0.9 + 1.0;
    }
    
    vector<vector<double>> dp(N+1, vector<double>(N+1, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= i; ++j) {
            chmax(dp[i+1][j], dp[i][j]);
            chmax(dp[i+1][j+1], dp[i][j] * 0.9 + P[i]);
        }
    }
    double res = -(1LL<<60);
    for (int j = 1; j <= N; ++j) {
        chmax(res, dp[N][j] / fac[j] - 1200.0 / sqrt(j));
    }
    cout << fixed << setprecision(10) << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 327 E - Maximize Ratin (水色, 475 点)

問題概要

制約

考えたこと

コード