"本资源是关于Codeforces (CF) 第1458场竞赛问题B (GlassHalfSpilled) 的详细解题报告,主要使用C++编程语言进行解答。"
在洛谷CF1458B题目中,我们面对的是一个与01背包问题相关的优化问题。题目要求我们考虑一序列的瓶子,每个瓶子有自己的容量`c[i]`和含水量`v[i]`。当选择一瓶时,它可以贡献`b_i`单位的水,如果不选择,则只能贡献`b_i / 2`单位的水。目标是确定一个子集,使得这些瓶子在不超过特定最大容量限制的情况下,能够获得最大的总水量。
解题的关键在于使用动态规划(Dynamic Programming, DP)来解决这个问题。设`dp[i][j]`表示前`i`个瓶子中选择一部分,使得最大容量为`j`时可以获得的最大水量。初始化`dp`数组为一个二维数组,大小为`110 x 10010`,这是因为瓶子的数量可能最多为110个,而容量可能达到10000。
动态规划的状态转移方程可以表示为:
```cpp
dp[i][j]=max(dp[i][j], min(double(j), dp[i-1][j-c[x]] + v[x]));
```
在这个方程中,`x`是当前处理的瓶子的下标。这意味着我们在当前容量`j`下,可以选择不放第`i`个瓶子(保持`dp[i][j]`不变),或者选择它,但要确保不超过总容量(即`j >= c[x]`),此时我们可以通过加入`v[x]`的水量。
在遍历所有瓶子后,我们需要找到第`i`个答案,即在不超出总容量的情况下,从剩余的水中尽可能多地添加水。这个答案可以通过遍历所有可能的容量`j`,并计算`dp[i][j]`加上不超过`((sum - dp[i][j]) / 2)`的剩余水量的最大值来得到。最终输出结果保留一位小数。
完整的C++代码如下:
```cpp
#include <bits/stdc++.h>
using namespace std;
double dp[110][10010];
int c[110], v[110];
int main() {
int n;
double sum = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &c[i], &v[i]);
sum += v[i];
}
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= 10000; j++) {
dp[i][j] = -1000000000.000000000;
}
}
for (int i = 1; i <= n; i++) {
for (int j = i; j >= 1; j--) {
for (int k = 10000; k >= c[i]; k--) {
dp[j][k] = max(dp[j][k], min(double(k), dp[j - 1][k - c[i]] + v[i]));
}
}
}
double ans = 0;
for (int j = 0; j <= 10000; j++) {
ans = max(ans, dp[n][j] + min(double(n - dp[n][j]), (sum - dp[n][j]) / 2));
}
printf("%.1f000000000", ans);
return 0;
}
```
这段代码实现了题目要求的算法,通过动态规划求解最大水量,并且在最后给出了保留一位小数的精确答案。