题解 | #牛牛去买球#

牛牛去买球

牛牛去买球 (nowcoder.com)

solve

简化问题 ， 找一个解：

1. 每一个包里面的红球、蓝色球的数量变化1。无论如何变化 ， 同色的球的数量至少为k。
2. 寻找满足上条件 ， 花费最低的解。

关注几种解结构：

1. 所有商品中 ， 红球的数量都减1。
2. 所有商品中，蓝球的数量都减1。

只考虑这两种情况是不全面的。如下：

但是还是遗漏了一些解：反例如下：

2 10
6 5
4 4
1 1

​ 该情况下 ， 无法做到两个减到最小值。但是两个都选了， 由于一个包里面球数量守恒，无论怎么变化依然满足条件。其关键是两种球数目之和大于等于$2\ast k-12*k\; -\; 1$。很显然，平均使得最大值最小，依然大于等于k.

​ 反之 ， 如果总的球数小于$2\ast k-12*k\; -\; 1$。解满足题意得充要条件是，两种球中的一种，减到极限了也依然满足数量大于等于k。前述两种情况下，01背包得到的就是这种解的最优值。

1. 不妨设当前的子问题为蓝色球（最劣情况）。显然$f_{i}f\_i$通过背包求解后，其解就是满足蓝色球减到极限了 ， 也满足题意的最小价值的解。那么我们枚举任意一种总球数小于2*k - 1的合法的（蓝色球减到极限，也满足大于等于k条件）解。显然可以属于上述子问题解集（并不一定是最优解，其实问题的解就是满足基本条件的解集中取最优值。）那么$f_{i}f\_i$更优。

2. 反之红色球亦然。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1E6 + 10;
const ll inf = 1E15;
int a[N] , b[N] , v[N];
//当前的最小值是什么？
//考虑了前i个商品。
//选择了多少个商品。
//是哪一类球更多
ll f[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n , k; cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++) cin >> v[i];
	ll ans = inf;
	memset(f , 0x3 , sizeof f);
	f[0] = 0;
	for (int i = 1; i <= n; i++) {
		int w = a[i] - 1;
		for (int j = 50000; j >= w ; j --)
			f[j] = min(f[j] , f[ j - w] + v[i]);
	}
	for (int i = k; i <= 500000; i++) {
		ans = min(ans , f[i]);
	}
	memset(f , 0x3 , sizeof f);
	f[0] = 0;
	for (int i = 1; i <= n; i++) {
		int w = b[i] - 1;
		for (int j = 50000; j >= w ; j --)
			f[j] = min(f[j] , f[j - w] + v[i]);
	}
	for (int i = k; i <= 500000; i++) {
		ans = min(ans , f[i]);
	}
	memset(f , 0x3 , sizeof f);

	f[0] = 0;
	for (int i = 1; i <= n; i++) {
		int w = b[i] + a[i];
		for (int j = 50000; j >= w ; j --)
			f[j] = min(f[j] , f[j - w] + v[i]);
	}
	for (int i = k * 2 - 1; i <= 500000; i++) {
		ans = min(ans , f[i]);
	}
	if (ans == inf) ans = -1;
	cout << ans << '\n';
}

/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/