题解 | #牛牛去买球#

分析

题目要求至少有 $K$ 个球同色，就有三种情况：（1） $a$ 球至少有 $K$ 个；（2） $b$ 球至少有 $K$ 个；（3） $a$ 和 $b$ 都至少有一种球是有 $K$ 个。

对于给定的 $(a_{i}, b_{i}, c_{i})$ 都有选择和不选两种方案，这就有点像01背包问题，我们只需要找出 $v$ 和 $w$ 是什么就行，很明显 $w$ 对应的就是 $c_{i}$ , 而至于 $v$ 就有三种情况。

但是由于有偏差，有三种情况； $(a_{i} + 1, b_{i} - 1), (a_{i}, b_{i}), (a_{i} - 1, b_{i} + 1)$
情况1：由于要保证 $a$ 至少有 $K$ 个球，所以此时的 $v$ 对应的就是 $a_{i} - 1$
情况2：由于要保证 $b$ 至少有 $K$ 个球，所以此时的 $v$ 对应的就是 $b_{i} - 1$
情况3：虽然有偏差，但是 $a_{i} + b_{i}$ 在对于每个盒子而言都是不变的，所以此时的 $v$ 对应的就是 $a_{i} + b_{i}$

状态表示 $f [i] [j]$ 表示考虑前 $i$ 个的选法中总体积恰好为 $j$ 总价值最少的方案的集合。
属性: $M i n$
状态计算： $f [i] = m i n (f [i - 1] [j], f [i] [j - v] + w$
对于01背包问题而言，优化到一维，只需要在枚举体积时从大到小枚举即可。

C++ 代码

#include <cstring>
#include <iostream>

using namespace std;

const int N = 60, M = 20010;

int n, m;
int a[N], b[N], c[N];
int f[M];

int work(int type)
{
    memset(f, 0x3f, sizeof f);
    
    f[0] = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int w;
        int v = c[i];
        if (type == 0) w = a[i] - 1;  // 情况1
        else if (type == 1) w = b[i] - 1;  // 情况2
        else w = a[i] + b[i];  // 情况3
        for (int j = M - 1; j >= w; j -- )
            f[j] = min(f[j], f[j - w] + v);
    }
    
    // 由于状态定义的是体积恰好是j, 所以要枚举大于等于m的所有情况
    int res = 0x3f3f3f3f;
    if (type <= 1)
    {
        for (int i = m; i < M; i ++ ) res = min(res, f[i]);
    }
    else
    {
        for (int i = m * 2 - 1; i < M; i ++ ) res = min(res, f[i]);
    }
    
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
    
    int ans = 0x3f3f3f3f;
    for (int i = 0; i < 3; i ++ )
        ans = min(ans, work(i));
    
    if (ans == 0x3f3f3f3f) puts("-1");
    else cout << ans << endl;
    
    return 0;
}