CF730J-Bottles

2022-07-25 题解

题目大意：有n个水瓶，给出每个水瓶的容量和里面原本装的水的数量。从一个瓶中向另外一个瓶中倒一个单位的水需要一个单位的时间。问：使这n个瓶中的水装到尽可能少的瓶中至少需要多少个单位的时间。

水能装到的尽可能少的瓶子数量就是从大到小拿瓶子，这个比较简单。

“时间”这个概念比较难维护。注意到：把所有水装到某些瓶子里所需最小时间是水的总量-这些瓶子原有水的总量。因此可以通过维护“瓶子中原有水量”间接得到时间。

令dp[j][k]表示：取j个瓶子，瓶子总容量至少为k时，这j个瓶子原本最多能有多少水量。之后类似01背包一样逐个用瓶子的信息更新背包。

#include <bits/stdc++.h>
#define int long long
using namespace std;
pair<int, int> p[105];
int dp[105][10005];
signed main()
{
    int n, i, j, k, sum = 0, res = 0;
    scanf("%lld", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%lld", &p[i].second);
        sum += p[i].second;
    }
    for (i = 1; i <= n; i++)
        scanf("%lld", &p[i].first);
    sort(p + 1, p + 1 + n);
    for (i = n; i; i--)
    {
        res += p[i].first;
        if (res >= sum)
            break;
    }
    res = n - i + 1;
    memset(dp, -12, sizeof(dp));
    dp[0][0] = 0;
    for (i = 1; i <= n; i++)
    {
        for (j = i; j; j--)
        {
            for (k = 10000; k >= 0; k--)
            {
                if (k >= p[i].first)
                    dp[j][k] = max({dp[j][k], dp[j][k + 1], dp[j - 1][k - p[i].first] + p[i].second});
                else
                    dp[j][k] = max(dp[j][k], dp[j][k + 1]);
            }
        }
    }
    printf("%lld %lld", res, sum - dp[res][sum]);
    return 0;
}