[CF1458B] Glass Half Spilled

[CF1458B] Glass Half Spilled

Description

有 (n le 100) 杯水，其中第 (i) 杯有容积 (a_i le 100) 单位，初始时装有 (b_i) 单位的水，可以进行若干次操作，每次选择一杯水的一定水量并倒到另一杯水中，每倒一次水，倒的水会有一半洒在地上，对于所有整数 (p) 满足 (1leq pleq n)，求出进行若干次操作后选取 (p) 个杯子能获得水单位数量的最大值。

Solution

单独考虑每个询问，显然我们划分为两个集合 A,B，将 B 中的所有水往 A 里倒，看够不够。问题是，A 如何选择不能简单按照 ai 或者 bi 来考虑
对于一个选择，所有 A 中的 a 和为 sum_a，所有 A 中 b 和为 sum_b，总的 b 和为 tot_b，那么答案为 min((sum_b+tot_b)/2, sum_a)

考虑一个背包，用 sum_a 作为容量，用 sum_b 作为权值，对于一个确定的 sum_a 我们想要的 sum_b 很显然会是最大的那个

设 (f[i][j]) 表示考虑了前 i 杯水，(sum_a=j) 时，(sum_b) 最大可以为多少，转移时无非就是枚举当前这一杯选还是不选

但这样没有办法解决杯数的问题

因此我们再加一维状态

设 (f[i][j][k]) 表示考虑了前 i 杯水，选了 j 个杯子当作最后的容器（也就是 sum 中的），切 (sum_a=k)，(sum_b) 最大可以是多少

那么最后，对于 p 的答案，我们只要从所有 j 个 p 的所有状态中选取最大即可

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

#define int long long
const int N = 105;
const int M = 10005;

int f[N][M], n, m, a[N], b[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    memset(f, 0xC0, sizeof f);
    f[0][0] = 0;
    int tot_b = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i], tot_b += b[i];
    for (int i = 1; i <= n; i++)
        for (int j = i; j >= 1; j--)
            for (int k = M - 1; k >= a[i]; k--)
                f[j][k] = max(f[j][k], f[j - 1][k - a[i]] + b[i]);
    for (int i = 1; i <= n; i++)
    {
        double ans = 0;
        for (int j = 0; j < M; j++)
            ans = max(ans, min((tot_b + f[i][j]) / 2.0, 1.0 * j));
        cout << fixed << setprecision(1) << ans << " ";
    }
}