Atcoder Beginner Contest 327E

Atcoder Beginner Contest 327E

E - Maximize Rating

问题描述

高桥君参加了$N$次竞赛，第 $i$ 次竞赛的成绩为 $ P_i $。

高桥君希望从中选择（至少一个）若干场竞赛，以使得从这些竞赛中计算得出的高桥君的评分最大化。

当选择合适的竞赛时，请求出可能的最大评分值。

假设高桥君选择了$k$场竞赛，并且在这些竞赛中获得的成绩依次为$ Q_1,Q_2,\cdots,Q_k $，则高桥君的评分$R$计算公式为：

$$R = \frac{\sum_{i = 1}^{k} (0.9)^{k - i} Q_i}{\sum_{i = 1}^{k} (0.9)^{k - i}} - \frac{1200}{\sqrt{k}}$$

算法

动态规划 背包dp

代码

#include <bits/stdc++.h>
#include <iomanip>
#define debug(a) cout<<#a<<"="<<a<<"\n"
#define EPS 1e-8
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define all(v) v.begin(),v.end()
using namespace std;
using i64 = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<long long,long long>;
static constexpr int ALPHABET_SIZE = 26;
static constexpr long double N = -1145141919810.0;
static constexpr int MOD = 998244353;

void solve() {
    //n个比赛中选k个, 使得结果最大
    // 1 <= k <= n
    //O(n ^ 2)
    //枚举K, dp[n][k]: 前n个比赛中选了k个比赛所得到的最大分数. long double
    int n;
    cin >> n;
    vector<long double> perf(n + 1, 0.0);
    for (int i = 1; i <= n; i++) {
        cin >> perf[i];
    }
    vector<vector<long double>> dp(n + 1, vector<long double>(n + 1, 0.00));
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= i; k++) {
            dp[i][k] = max(dp[i - 1][k], dp[i - 1][k - 1] * 0.9 + perf[i]);
        }
    }

    vector<long double> sum(n + 1);
    long double res = N;
    for (int k = 1; k <= n; k++) {
        sum[k] = sum[k - 1] * 0.9 + 1.0;
        res = max(res, dp[n][k] * 1.0 / sum[k] - 1200.00 / sqrt(k)); 
    }
    cout << fixed << setprecision(12) << res;
}

int main()
{
    IOS;
    int t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
    return 0;     
}