题解 CF366C Dima and Salad

hellhell · 2022-05-04 16:30:20 · 个人记录

题目描述

有 n 个水果，每个水果有两个属性：美味值和卡路里值。

现在选用若干个（至少 1 个）水果制作一份特殊的沙拉，沙拉的美味值为所选的水果的美味值的和，沙拉的卡路里值为所选水果的卡路里值的和。

沙拉的美味值恰好是卡路里值的 K 倍。请计算该沙拉美味值最大为多少。

第一行，两个整数 n, k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10)；

第二行，包含 n 个整数，a_1, a_2, ..., a_n (1 ≤ ai ≤ 100)，表示水果的美味值；

第三行，包含 n 个整数，b_1, b_2, ..., b_n (1 ≤ bi ≤ 100)，表示水果的卡路里值。

【输出数据】共一行，一个整数，表示最大美味值，若无解则输出 -1。

思路分析

看上去就是一个 0/1 背包，但如果只把卡路里值当做质量，把美味值当做价值，在转移时需要考虑两者的关系，也就是需要同时关注 dp 数组的下标和存储值。这看起来无法实现。

既然要求美味值要是卡路里值的 k 倍，不如直接拿 a_i-k\times b_i 当做质量，拿 a_i 当做价值。

这样就可以当成普通的 0/1 背包来做了。注意 a_i-k\times b_i 可能是负数。

据说这里的转化运用了分数规划的思想。。。

代码实现

#include <bits/stdc++.h>
#define int long long

using namespace std;

int read(){
    int res=0;
    int f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*f;
}

const int maxn=105;

int n,k;
int a[maxn],b[maxn],c[maxn];
int dp[100005],g[100005];
int ans=-1;

signed main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=n;i++)
        b[i]=read(),c[i]=a[i]-k*b[i];
    for(int i=1;i<=10000;i++){
        dp[i]=g[i]=-0x3f3f3f3f;
    }
    for(int i=1;i<=n;i++){
        if(c[i]<0){
            for(int j=10000;j>=-c[i];j--){
                g[j]=max(g[j],g[j+c[i]]+a[i]);
            }
        }
        else{
            for(int j=10000;j>=c[i];j--){
                dp[j]=max(dp[j],dp[j-c[i]]+a[i]);
            }
        }
    }
    for(int j=10000;j>=0;j--){
        ans=max(ans,dp[j]+g[j]);
    }
    if(ans!=0)
        printf("%lld\n",ans);
    else
        printf("-1\n");
    return 0;
}