A21006.国王饮水记
2025-04-13 11:27:21
发布于：浙江
#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;
}
全部评论 9
/code/judger/run/20260714/5119178782529290337/main.cpp: In function 'int main()':
/code/judger/run/20260714/5119178782529290337/main.cpp:10:24: error: expected ';' before ')' token
10 | for (int i = 1; i++) {
| ^
| ;
/code/judger/run/20260714/5119178782529290337/main.cpp:11:24: error: 'h' was not declared in this scope
11 | scanf("%lld", &h[i]);
| ^
/code/judger/run/20260714/5119178782529290337/main.cpp:13:10: error: 'h' was not declared in this scope
13 | sort(h + 1, h + n + 1); // 按水位排序
| ^
compilation terminated due to -fmax-errors=3.
???2026-08-09 来自 浙江
0/code/judger/run/20260806/5123383288093737058/main.cpp: In function 'int main()':
/code/judger/run/20260806/5123383288093737058/main.cpp:10:24: error: expected ';' before ')' token
10 | for (int i = 1; i++) {
| ^
| ;
/code/judger/run/20260806/5123383288093737058/main.cpp:11:24: error: 'h' was not declared in this scope
11 | scanf("%lld", &h[i]);
| ^
/code/judger/run/20260806/5123383288093737058/main.cpp:13:10: error: 'h' was not declared in this scope
13 | sort(h + 1, h + n + 1); // 按水位排序
| ^
compilation terminated due to -fmax-errors=3.？？？
2026-08-06 来自 浙江
0/code/judger/run/20260411/5102194592923517025/main.cpp: In function 'int main()':
/code/judger/run/20260411/5102194592923517025/main.cpp:10:24: error: expected ';' before ')' token
10 | for (int i = 1; i++) {
| ^
| ;
/code/judger/run/20260411/5102194592923517025/main.cpp:11:24: error: 'h' was not declared in this scope
11 | scanf("%lld", &h[i]);
| ^
/code/judger/run/20260411/5102194592923517025/main.cpp:13:10: error: 'h' was not declared in this scope
13 | sort(h + 1, h + n + 1); // 按水位排序
| ^
compilation terminated due to -fmax-errors=3.2026-04-11 来自 重庆
0
有帮助，赞一个