366 C.Dima and Salad

不会写...看的题解,wsfw

物品的两个属性不太好弄

假如暴力设计状态,就是定义 $f[num][i][j]$ 表示在 $[1,num]$ 中 $\sum a=i$ 且 $\sum b=j$ 的状态是否存在

暴力枚举的话复杂度上天

换种思路

考虑到最后的合法方案是 $\frac{\sum\limits_{i=1}^ma_i}{\sum\limits_{i=1}^mb_i}=k$

也就是 $\sum\limits_{i=1}^ma_i=k\sum\limits_{i=1}^mb_i$

不妨给所有 $b_i$ 扩大到 $kb_i$ ,这样一来我们只需要关注当前选择两种属性的偏移量

如果偏移量为零,那么达到目的

因为 $\sum a_i<=10000$

所以偏移量不会超过这么多,再算上 $100$ 个物品

实现复杂度和空间复杂度最坏是 $20000*100=2*10^6$

定义 $f[i][j]$ 为前 $i$ 个物品的偏移量为 $j$ 时最大的 $\sum a$

问题得到解

注意一下这个 $01$ 背包的物品由于有正数有负数,所以不能只开一维

(假如只开一维,需要分物品价值正数和负数分两次转移)

#include <bits/stdc++.h>
using namespace std;
const int base = 10000;
int n,k,f[109][20009],a[109],b[109];
signed main()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)    cin >> a[i];
    for(int i=1;i<=n;i++)    cin >> b[i];
    memset( f,-0x3f,sizeof f);
    int inf = f[0][0];
    f[0][base] = 0;
    for(int i=1;i<=n;i++)
    {
        int pian = a[i]-b[i]*k;
        for(int j=-base;j<=base;j++)
        {
            if( j-pian+base<=20000&&j-pian+base>=0 )
                f[i][j+base] = max( f[i-1][j+base],f[i-1][j-pian+base]+a[i] );
        }
    }
    if( f[n][base]==0 )    f[n][base] = -1;
    cout << f[n][base];
}