CodeForces - 788C - 完全背包

-zzuxx- / 2024-11-17 / 原文

题目表示（x1 * a[1] + x2 * a[2] + ... + xk * a[k]) / ((x1 + x2 + ... + xk) * 1000) = n / 1000，可以推出（x1 * a[1] + x2 * a[2] + ... + xk * a[k]) = n * (x1 + x2 + ... + xk)，
进而得出（x1 * （a[1] - n) + x2 * (a[2] - n) + ... + xk * (a[k] - n)) = 0，这样处理之后就和我之前做的一道01背包的题很像CodeForces - 366C，将所有a[i] = a[i] - n，再分别对a[i] > 0 和 a[i] <= 0进行完全背包，最后找min(dp1[i] + dp2[i], mn)~~可能讲的不是很清楚，建议大家先做一下链接的题再回来看我这些话，可能会明朗一些。~~

但如果直接进行我上述的操作会有两点问题：1. k = 1e6，直接操作的话，完全背包光第一层循环就已经1e6了，太容易爆时间复杂度了；2. 对于第二层循环的大小（即背包容量）该如何确定？

对于第一个问题，k = 1e6，但a[i] <= 1e3，所以有效部分最多1e3，所以k的范围是假的，可以通过去重操作来缩小k
对于第二个问题，完全背包第二层循环一般为背包容量，处理过后的a[i]就是每个物品所占的空间大小，为了让背包容量达到极限大，我们处理之后的a[i]之间需要没有倍数关系
然后因为n是确定的,如果我们需要让~~处理前的形式~~(a[i1] - n) * (a[i2] - n)最大，n = 499，a[i1] = 1000，a[i2] = 0时，乘积最大，结果为501 * 499。
下面放代码：

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

ll dp2[1000010], dp1[1000010];
ll a[1000010];
int main(){
    ll n, k, num;
    bool judge = 0;
    cin >> n >> k;
    for(ll i = 1; i <= k; i ++){
        cin >> num;
        a[i] = n - num;
        if(num == n)
        	judge = 1;
    }
    if(judge == 1){
    	cout << 1 << endl;
    	return 0;
	}
    memset(dp1, 127, sizeof(dp1));
    memset(dp2, 127, sizeof(dp2));
    sort(a + 1, a + 1 + k);
    k = unique(a + 1, a + 1 + k) - a - 1;
    ll w = 501 * 499 + 10;
    dp1[0] = 0, dp2[0] = 0;
    for(ll i = 1; i <= k; i ++){
        if(a[i] > 0)
            for(ll j = 0; j <= w - a[i]; j ++){
                dp1[j + a[i]] = min(dp1[j + a[i]], dp1[j] + 1);
            }
        else
            for(ll j = 0; j <= w - a[i]; j ++){
                dp2[j - a[i]] = min(dp2[j - a[i]], dp2[j] + 1);
            }
    }
    ll mn = 1e18;
    for(ll i = 1; i <= w; i ++){
    	if(dp1[i] != dp1[1000005] && dp2[i] != dp2[1000005])
        	mn = min(dp1[i] + dp2[i], mn);
    }
    if(mn == 1e18){
        cout << "-1" << endl;
    }
    else{
        cout << mn << endl;
    }
    return 0;
}

对于背包容量的问题，我一直没想明白，就拖着，今天又继续想，大概想明白了，可能表述还是太模糊了，大家可以理解理解 ~~我还是太蒻了，加油吧~~