题解 CF1458B 【Glass Half Spilled】
Warriors_Cat
2020-12-23 17:10:49
[题面传送门](https://www.luogu.com.cn/problem/CF1458B)。
> 题意：有 $n$ 杯水，现有 $a_i$ 单位水，容积为 $b_i$ 单位水。将现有 $c_i$ 单位水中 $x(x \le c_i)$ 单位水倒入现有 $c_j$ 单位水后，$c_i$ 会变成 $c_i - x$，$c_j$ 会变成 $\min\{b_j, c_j + \frac{x}{2}\}$。对于每个 $k \in [1, n]$，问经过若干次操作后取 $k$ 个杯子最多能有多少水。
---
### $Solution:$
现场被区分了，没想出来，赛后发现没有多难。
有一个很重要的性质：对于三个杯子 $x, y, z$，将 $x$ 倒进 $y$、再将 $y$ 倒进 $z$ 还不如将 $x$ 倒进 $z$、再将 $y$ 倒进 $z$。
因此问题就转化为：选取 $k$ 个杯子，将其他杯子里的水倒入这 $k$ 个杯子，最后最多能倒多少。
这样就只是一个背包问题了。定义 $f_{i, j, k}$ 表示前 $i$ 个杯子中选 $j$ 个，此时 $b_i$ 和为 $k$ 时 $a_i$ 和的最大值。至于状态转移，从 $f_{i - 1, j - 1, k - b_i} + a_i$ 即可。
over，时间复杂度为 $O(n^3V)$，其中 $V$ 为值域。
---
### $Code:$
非赛时代码，码风可能有些不一样。
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = y; i >= x; --i)
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 100;
int n, a[N + 5], b[N + 5], sum, f[N + 5][N + 5][N * N + 5]; double ans[N];
inline void work(){
n = read(); rep(i, 1, n) b[i] = read(), sum += (a[i] = read());
memset(f, -0x3f, sizeof(f)); rep(i, 0, n) f[i][0][0] = 0;
rep(i, 1, n) rep(j, 1, i) rep(k, 0, N * N){
f[i][j][k] = f[i - 1][j][k];
if(k >= b[i]) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - b[i]] + a[i]);
}
rep(i, 1, n) rep(j, 0, N * N) ans[i] = max(ans[i], min(1.0 * j, 1.0 * (sum + f[n][i][j]) / 2));
rep(i, 1, n) printf("%0.11lf ", ans[i]);
}
int main(){ int t = 1; while(t--) work(); return 0; }
```