Glass Half Spilled
题意
在编号为 1的桌子上有 n个玻璃杯，第 i个杯子可以容纳最多 a i单位水，当前包含 b i单位水。
选择k 个玻璃杯，并尽可能多地收集水。为了达到这个效果，你可以把水从一个玻璃杯倒到另一个玻璃杯，想倒多少次就倒多少次 然而，每次你试图转移任何数量的水时，都会有一半的水洒在地板上。对于每个 k = 1 、 2 、 3 、 … n ，确定在零次或多次在玻璃杯之间转移水后，任意选择的k个玻璃杯可以收集的最大可能总量。
思路
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 110; int n; int a[N], b[N]; double dp[2][N][N * N]; void solve() { cin >> n; int suma = 0, sumb = 0; for (int i = 1; i <= n; ++i) { scanf("%d %d", &a[i], &b[i]); suma += a[i]; sumb += b[i]; } //预处理 for (int j = 0; j <= n; ++j) for (int k = 0; k <= suma; ++k) dp[0][j][k] = -INF; dp[0][0][0] = 0; // int t = 1;//滚动数组 for (int i = 1; i <= n; ++i,t ^= 1) { for (int j = 0; j <= n; ++j) //不选第i个杯子 for (int k = 0; k <= suma; ++k) dp[t][j][k] = dp[t ^ 1][j][k]; for (int j = 1; j <= n; ++j) //选第i个杯子 for (int k = a[i]; k <= suma; ++k) dp[t][j][k] = max(dp[t][j][k], dp[t ^ 1][j - 1][k - a[i]] + b[i]); } for (int j = 1; j <= n; ++j) { double res = 0; for (int k = 0; k <= suma; ++k) res = max(res, min(double (2.0 * k), dp[t ^ 1][j][k] + sumb)); printf("%.10lf ", res / 2); } cout << endl; } int main() { //int t; cin >> t; //while (t--) solve(); return 0; }
