题解：P7801 [COCI 2015/2016 #6] KRUMPIRKO

· · 题解

P7801 [COCI 2015/2016 #6] KRUMPIRKO

Tag：DP

考虑能不能直接 DP，发现不好计算。

发现答案是分数的形式，考虑 01分数规划，但分子分母并不是关于 a_i 和 c_i 的一次多项式，因此也不行。

首先这个题目的答案有两个未知数，不太好处理，我们把它变换为：

\frac{s_1(c)\cdot(s(c)-s_1(c))}{s_1(a)\cdot(s(a)-s_1(a))}

其中 s_1 表示填入第一家商店的物品的某个属性之和，s 表示总和。那么 s 是常数，于是就只有一个未知量了。

现在还有一个问题，我们不能和平常一样，固定一些已经选出的物品，然后考虑新增的物品，因为这样取 \min 转移的局部最优解，不代表全局最优。

这时候你会发现题目还有一个性质没用上：\sum a_i\le 500。

我们直接枚举 s_1(a)，因为它比较小。然后考虑 s_1(a) 固定时，怎么取到最小答案：由于分母固定，那么要求分子尽量小，而我们发现分子是一个开口向下的二次函数，显然在 s_1(c) 取到 \min 或 \max 时该函数取到最小。

于是现在问题就转换为：求选择 L 个物品，使得它们的 a_i 之和为 s_1(a)，并且 c_i 之和最大或最小。

这个可以直接 DP，设 f(i,j,k) 表示考虑前 i 个物品，选了 j 个，a_i 之和为 k 的最大 c_i 之和，最小同理。然后空间可能会爆，用滚动数组转移即可。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using UI = unsigned int;
using ULL = unsigned long long;
using DB = double;
using LDB = long double;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
#define CP(x) complex<x>
#define fst first
#define snd second
#define popcnt(i) __builtin_popcount(i)

const int N = 1e2 + 5, V = 5e2 + 5;
const LL INF = 2e18;

int n, m;
LL suma, sumb, a[N], b[N], f[2][N][V], g[2][N][V];
// f: max, g: min

LDB val(LL sa, LL sb) {
    if (sb == INF || sb == -INF) return INF;
    return (DB)(sumb - sb) * sb / ((suma - sa) * sa);
}

void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        suma += a[i];
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &b[i]);
        sumb += b[i];
    }
    int cur = 0;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= suma; j++) {
            f[0][i][j] = -INF;
            g[0][i][j] = INF;
        }
    }
    f[0][0][0] = g[0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        cur ^= 1;
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= suma; k++) {
                f[cur][j][k] = f[cur ^ 1][j][k];
                if (j && k >= a[i] && f[cur ^ 1][j - 1][k - a[i]] != -INF) {
                    f[cur][j][k] = max(f[cur][j][k], f[cur ^ 1][j - 1][k - a[i]] + b[i]);
                }
                g[cur][j][k] = g[cur ^ 1][j][k];
                if (j && k >= a[i] && g[cur ^ 1][j - 1][k - a[i]] != INF) {
                    g[cur][j][k] = min(g[cur][j][k], g[cur ^ 1][j - 1][k - a[i]] + b[i]);
                }
            }
        }
    }
    LDB ans = INF;
    for (int i = 0; i <= suma; i++) {
        ans = min({ans, val(i, f[cur][m][i]), val(i, g[cur][m][i])});
    }
    printf("%.3Lf\n", ans);
}

int main() {
    solve();
    return 0;
}