【题解】Dima and Salad CodeForces - 366C⭐⭐⭐ 【01背包 思维】

Dima and Salad CodeForces - 366C

有n个水果, 每个水果都有两个属性值ai表示美味程度, bi表示能量值, 现在要求选出一个或多个水果, 使得选出的水果的ai和与bi和的比例是k 问在这种清形可能出现的情况下ai的和最多是多少, 如果这样的情形不存在输出 -1

Input

第一行包含两个整数n, k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10). 第二行为 n个整数 a1, a2, …, an (1 ≤ ai ≤ 100) — 水果的美味值. 第三行包含 n 个整数: b1, b2, …, bn (1 ≤ bi ≤ 100), 表示 —水果的能量值.

Output

如果无解输出-1.
否则输出满足条件的ai累加和

Examples

Input
3 2
10 8 1
2 7 1
Output
18
Input
5 3
4 4 4 4 4
2 2 2 2 2
Output
-1

Hint

In the first test sample we can get the total taste of the fruits equal to 18 if we choose fruit number 1 and fruit number 2, then the total calories will equal 9. The condition fulfills, that’s exactly what Inna wants.
In the second test sample we cannot choose the fruits so as to follow Inna’s principle.

题意:

题解:

先看题面, 多个物品选多个, 每个只选一次, 很显然的01背包问题
再仔细分析一下, 显然此题并不是一道直接的01背包问题, 价值和花费都没有明显给出, 我们此刻的思路便是寻找可作为价值的属性, 价值一旦确定, 状态转移方程自然迎刃而解
根据题中给出的$\sum$a/$\sum$b == K, 可以推出$\sum$a - K*$\sum$b == 0
这样一来, 我我们可以发现对于每一个bi, 我们只关心ai - k*bi的值, 把它作为花费(也就是价值就好了)
因为可能存在负值的问题, 我们定义两个dp一个遍历正的, 一个遍历负的, 最后求一下和就好了
注意数据范围

小结

看到数学公式就去推公式, 看到隐含的数学公式先写出来.
仔细考虑所有情况, 比如负值问题

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ms(x, n) memset(x,n,sizeof(x));
typedef  long long LL;
const int inf = 1<<30;
const LL maxn = 110;

struct node{
    int v, cost;  //a的值和a[i]-k*b[i]的值
}a[1500];
int N, K, dp1[100*150], dp2[100*150]; //dp表示花费不超过j的最大和
int solve(){
    ms(dp1, -0x3f3f3f3f);
    ms(dp2, -0x3f3f3f3f);
    dp1[1] = dp2[1] = 0;

    for(int i = 1; i <= N; i++){
        if(a[i].cost>=0){
            for(int j=100*105; j >= a[i].cost; j--)
                dp1[j] = max(dp1[j], dp1[j-a[i].cost]+a[i].v);
        }else{
            a[i].cost = -a[i].cost; //负数取正
            for(int j=100*105; j >= a[i].cost; j--)
                dp2[j] = max(dp2[j], dp2[j-a[i].cost]+a[i].v);
        }
    }
    int ans = -1;
    for(int i = 0; i <= 100*105; i++){
        if(dp1[i]+dp2[i]!=0 && dp1[i]+dp2[i]>ans)
            ans = dp1[i]+dp2[i];
    }
    return ans;
}
int main()
{
    cin >> N >> K;
    for(int i = 1; i <= N; i++)
        cin >> a[i].v;
    int b;
    for(int i = 1; i <= N; i++)
        cin >> b, a[i].cost = a[i].v-K*b;

    cout << solve() << endl;
	return 0;
}