[CF366C Dima and Salad] 题解

不错的背包题。

题解正文

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

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

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

想到要满足最后的 ，就不难想到将 作为 背包的重量，然后 作为价值，最后 即是答案。我们可以正负分开处理，对于 的 按照正常的 背包转移，将 的将 视为 开另外的背包来跑，这两个 数组代表的意义分别为：质量为 的时候的最大价值以及质量为 的时候的最大价值。

那么 表示的就是最终的答案，遍历整个 数组取 即可。

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