Cf 730J Bottles
题意:
一共有n个瓶子,给出每个瓶子当前的水量和当前的容量。
将一瓶水中1ml水转移到别的瓶子上需要1s
求在使用最少瓶子数的前提下,转移需要的时间最少。
数据范围:
思路:
贪心+dp
可以贪心得到,最少需要使用的瓶子数量
然后现在已知最少瓶子数量,求需要转移的最少时间。
贪心的想,在瓶子数量一定的时候,我们肯定想这些瓶子里面的装的水尽可能多,因为水总数量是一定的,不是原有瓶子的水都需要花费1个单位时间。
然后我们选择出瓶子的时候,还需要确保瓶子的容量,所以状态有以下定义
实现:
#include <stdio.h>
#include <algorithm>
#define int long long
using namespace std;
const int N = 105;
int a[N], b[N];
int f[N][N * N]; //当前使用i个瓶子,这i个瓶子的容量为j,这些瓶子里面最多有f[i][j]ml的水
signed main()
{
int n;
scanf("%lld", &n);
int sum = 0;
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
sum += a[i];
}
for (int i = 1; i <= n; i++)
scanf("%lld", &b[i]);
for (int i = 0; i < N; i++)
for (int j = 0; j < N * N; j++)
f[i][j] = -1e18;
f[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = i; j; j--)
for (int k = b[i]; k < N * N; k++)
f[j][k] = max(f[j][k], f[j - 1][k - b[i]] + a[i]);
int re1 = 0, tot = 0;
sort(b + 1, b + 1 + n);
for (int i = n; i >= 0; i--)
{
re1++,
tot += b[i];
if (tot >= sum)
break;
}
int re2 = 0;
for (int i = sum; i < N * N; i++)
re2 = max(re2, f[re1][i]);
printf("%lld %lld\n", re1, sum - re2);
return 0;
}
标签:Bottles,int,sum,Cf,瓶子,re2,最少,730J
From: https://www.cnblogs.com/zxr000/p/17004791.html