366 C.Dima and Salad

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

物品的两个属性不太好弄

假如暴力设计状态,就是定义表示在中且的状态是否存在

暴力枚举的话复杂度上天

换种思路

考虑到最后的合法方案是

也就是

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

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

因为

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

实现复杂度和空间复杂度最坏是

定义为前个物品的偏移量为时最大的

问题得到解

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

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

#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];
}