[CF366C Dima and Salad] 题解

不错的背包题。

题解正文

首先我们最朴素的想法是什么？

枚举每一个美味值以及每一个卡路里值，用 bool 数组存下来判断是否可达，这样子的空间复杂度是 O( $10^8$ ) 的，时间复杂度是: O( $10^{10}$ )的。

首先上面的做法肯定是不行的，那么怎么办呢？

想到要满足最后的 $\sum{A_i} - \sum{B_i * k} == 0$ ，就不难想到将 $C_i = A_i - B_i * k$ 作为 $01$ 背包的重量，然后 $A_i$ 作为价值，最后 $dp[0]$ 即是答案。我们可以正负分开处理，对于 $> 0$ 的 $C_i$ 按照正常的 $01$ 背包转移，将 $C_i <= 0$ 的将 $C_i$ 视为 $|C_i|$ 开另外的背包来跑，这两个 $dp[i]$ 数组代表的意义分别为：质量为 $i$ 的时候的最大价值以及质量为 $-i$ 的时候的最大价值。

那么 $dp1[i] + dp2[i]$ 表示的就是最终的答案，遍历整个 $dp$ 数组取 $max$ 即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 50;
typedef long long LL;
LL n,k,A[MAXN],B[MAXN],C[MAXN];
LL dp1[100005],dp2[100005];
int main() {
    cin >> n >> k;
    for(int i = 1 ; i <= 100000 ; i ++) dp1[i] = dp2[i] = -1e9;
    for(int i = 1 ; i <= n ; i ++) cin >> A[i];
    for(int i = 1 ; i <= n ; i ++) cin >> B[i],C[i] = A[i] - B[i] * k;
    for(int i = 1 ; i <= n ; i ++) {
        if(C[i] <= 0) 
            for(int j = 100000 ; j >= -C[i] ; j --)
            dp2[j] = max(dp2[j + C[i]] + A[i] , dp2[j]);
        else 
            for(int j = 100000 ; j >= C[i] ; j --) 
            dp1[j] = max(dp1[j - C[i]] + A[i],dp1[j]);
    }LL Ans = -1e9;
    for(int i = 0 ; i <= 100000; i ++)Ans = max(Ans , dp1[i] + dp2[i]);
    Ans > 0 ? cout << Ans : cout << -1;
    return 0;
}