A731.表达式计算

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 8000;
int n, k, p[MAX_N + 1], sum[MAX_N + 1];
double dp[2][MAX_N + 1]; // 使用滚动数组优化空间

int main() {
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 1; i++) {
        scanf("%lld", &h[i]);
    }
    sort(h + 1, h + n + 1); // 按水位排序
    reverse(h + 1, h + n + 1); //  预处理前缀和
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + h[i];
    }

    // 初始化 DP
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        dp[0][i] = max(dp[0][i - 1], (double)h[i]); // 不进行任何操作
    }

    // 动态规划
    = 1; j <= min(k, n); j++) { // 枚举操作次数
        for (int i = 1; i <= { // 枚举前 i 个城市
            dp[j % 2][i] = dp[(j - 1) % 2][i]; // 不选择新的城市
            for (int l = 1; l <= i; l++) { //操作的区间长度
                double avg = (double)(sum[i] - sum[i - l]) / l;
                dp[j % 2][i] = max(dp[j % 2][i], dp[(j - 1) % 2][i - l] + avg);
            }
        }
    }

    // 输出结果
    printf("%.lf\n", dp[k % 2][n]);

    return 0;
}