链接
https://codeforces.com/contest/1459/problem/D
题意
$n(n\le 100)$ 个水杯，第 $i$ 个水杯容量为 $a_i(a_i\le 100)$，初始水量为 $b_i(b_i\le 100)$。
定义一次操作为从一个水杯取 $x$ 单位水，$x/2$ 单位水倒入另一个水杯（不能溢出），其余舍去。
求无限次操作后，选择 $1 \sim n$ 个水杯能获得的最大水量。
思路
记 $dp_{i,j,k}$ 前 $i$ 个选 $j$ 个总容量为 $k$ 的水杯的最大初始水量（该 j 个水杯作为容器，不进行操作），$B$ 为 $n$ 个水杯的总水量：
$dp_{i,j,k}=\min(dp_{i-1,j,k},dp_{i-1,j-1,k-a_i}+b_i)$。
取 $j$ 个水杯，在无限次操作后能获得的水量为 $\min \limits {1\le k \le 10000}(k,dp{j,k}+(B-dp_{j,k})/2)$。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=105;
int n,a[N],b[N],dp[N][N*N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
int sum=0;
for(int i=1;i<=n;i++) {
cin>>a[i]>>b[i];
sum+=b[i];
}
memset(dp,0xc0,sizeof dp);
for(int i=0;i<=n;i++) dp[i][0]=0;
for(int i=1;i<=n;i++) {
for(int j=n;j>=1;j--) {
for(int k=a[i];k<=10000;k++) {
dp[j][k]=max(dp[j][k],dp[j-1][k-a[i]]+b[i]);
}
}
}
cout<<fixed<<setprecision(10);
for(int i=1;i<=n;i++) {
int mx=0;
for(int j=1;j<=10000;j++) {
mx=max(mx,min(2*j,dp[i][j]+sum));
}
cout<<mx/2.0<<' ';
}
cout<<'\n';
return 0;
}
|