C. Dima and Salad

题意

有n种水果，第i个水果有一个美味度a_i和能量值b_i,现在要选择部分水果做沙拉，假如此时选择了m个水果，要保证\(\frac{\sum_{i=1}^ma_i}{\sum_{i=1}^mb_i}==k\)，问沙拉最大的美味度是多少？

思路

01背包变形。

对于给出的公式，我们化简一下：

\(\sum_{i=1}^ma_i-k*\sum_{i=1}^mb_i==0\)

就变成了把a[i]-k*b[i]作为体积，a[i]作为价值，向容量为0的背包里放，可以取得的最大价值。

因为a[i]-k*b[i]有正负，所以我们可以分别对正体积和负体积DP，体积为0直接算到答案中，在正负的DP值之中选择体积绝对值相等的最大和。

代码

//#include<bits/stdc++.h>

#include<vector>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<string>

#include<math.h>

#include<queue>

#include<map>

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int N=1e5+10;

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

struct note

{

    int a,b;

    int wei;

} arr[N];

int dp1[N],dp2[N];

int main()

{

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=1; i<=n; i++)

        scanf("%d",&arr[i].a);

    int spos=0,sneg=0,ans=0;

    for(int i=1; i<=n; i++)

    {

        scanf("%d",&arr[i].b);

        int tmp=arr[i].a-k*arr[i].b;

        arr[i].wei=tmp;

        if(tmp>0)

            spos+=tmp;//正体积的和

        else if(tmp<0)

            sneg-=tmp;//负体积的和

        else

            ans+=arr[i].a;//体积为0直接算贡献

    }

    memset(dp1,0x8f,sizeof(dp1));

    memset(dp2,0x8f,sizeof(dp2));

    dp1[0]=dp2[0]=0;

    for(int i=1; i<=n; i++)//正

    {

        if(arr[i].wei<=0)

            continue;

        for(int j=spos; j>=arr[i].wei; j--)

            dp1[j]=max(dp1[j],dp1[j-arr[i].wei]+arr[i].a);

    }

    for(int i=1; i<=n; i++)//负

    {

        if(arr[i].wei>=0)

            continue;

        for(int j=sneg; j>=-arr[i].wei; j--)

            dp2[j]=max(dp2[j],dp2[j+arr[i].wei]+arr[i].a);

    }

    int rel=0;

    for(int i=1; i<=min(sneg,spos); i++)//选择两个体积绝对值相等的最大值

    {

        if(dp1[i]>0&&dp2[i]>0)

            rel=max(rel,dp1[i]+dp2[i]);

    }

    ans+=rel;

    if(ans==0)

        printf("-1\n");

    else

        printf("%d\n",ans);

    return 0;

}

巴特西

CF#214 C. Dima and Salad 01背包变形

C. Dima and Salad

题意

思路

代码

最新文章

热门文章