专栏文章

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

cchenwenmo
P7801题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip3z7uc
此快照首次捕获于
2025/12/03 05:47
3 个月前
此快照最后确认于
2025/12/03 05:47
3 个月前
查看原文
P7801 [COCI 2015/2016 #6] KRUMPIRKO
Tag：DP
考虑能不能直接 DP，发现不好计算。
发现答案是分数的形式，考虑 01分数规划，但分子分母并不是关于 aia_i 和 cic_i 的一次多项式，因此也不行。
首先这个题目的答案有两个未知数，不太好处理，我们把它变换为：
s1(c)⋅(s(c)−s1(c))s1(a)⋅(s(a)−s1(a))\frac{s_1(c)\cdot(s(c)-s_1(c))}{s_1(a)\cdot(s(a)-s_1(a))}
其中 s1s_1 表示填入第一家商店的物品的某个属性之和，ss 表示总和。那么 ss 是常数，于是就只有一个未知量了。
现在还有一个问题，我们不能和平常一样，固定一些已经选出的物品，然后考虑新增的物品，因为这样取 min⁡\min 转移的局部最优解，不代表全局最优。
这时候你会发现题目还有一个性质没用上：∑ai≤500\sum a_i\le 500。
我们直接枚举 s1(a)s_1(a)，因为它比较小。然后考虑 s1(a)s_1(a) 固定时，怎么取到最小答案：由于分母固定，那么要求分子尽量小，而我们发现分子是一个开口向下的二次函数，显然在 s1(c)s_1(c) 取到 min⁡\min 或 max⁡\max 时该函数取到最小。
于是现在问题就转换为：求选择 LL 个物品，使得它们的 aia_i 之和为 s1(a)s_1(a)，并且 cic_i 之和最大或最小。
这个可以直接 DP，设 f(i,j,k)f(i,j,k) 表示考虑前 ii 个物品，选了 jj 个，aia_i 之和为 kk 的最大 cic_i 之和，最小同理。然后空间可能会爆，用滚动数组转移即可。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...