当前位置: 首页 > 工具软件 > Salad > 使用案例 >

CodeForces 366C Dima and Salad

燕昊东
2023-12-01

题意::n个物品,k为倍数。每个物品有两个属性(ai和bi),求在满足所取物品的a属性和是b属性和的k倍的前提下,问a属性的最大值是多少,具体看样例解释,很清楚。

思路:这个题真的是学到了, 对于公式进行变换,然后转化为一部分正数和一部分负数,然后分别求背包,,对于背包,之前一直有一个误区。正确的应该是对于dp[i[代表i体积全部装满所代表的最大价值,因为他可以从背包的转移方程中的出dp[i]=max(dp[i],dp[i-c[i]]+a[i]);这个方程中指出,目前的答案是由减去体积的地方转移来的,而01背包是倒着进行计算,所以的到满体积时的价值

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=105;
int n,k,a[maxn],b[maxn],c[maxn],dp[10005],pp[10006];

int main()
{
    while(~scanf("%d%d",&n,&k)){
        memset(dp,-0x3f,sizeof(dp));
        memset(pp,-0x3f,sizeof(pp));
//        memset(c,0,sizeof(c));
        dp[0]=pp[0]=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=0;i<n;i++){
            scanf("%d",&b[i]);
        }
        for(int i=0;i<n;i++){
            c[i]=a[i]-k*b[i];
        }
        for(int i=0;i<n;i++){
            if(c[i]>=0){
                for(int j=10000;j>=c[i];j--){
                    dp[j]=max(dp[j],dp[j-c[i]]+a[i]);
                }
            }
        }
        for(int i=0;i<n;i++){
            if(c[i]<0){
                c[i]=-c[i];
                for(int j=10000;j>=c[i];j--){
                    pp[j]=max(pp[j],pp[j-c[i]]+a[i]);
                }
            }
        }
        int ans=-1;
        for(int i=0;i<=10000;i++){
            if(dp[i]==0&&pp[i]==0)continue;
            else ans=max(ans,dp[i]+pp[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

转载于:https://www.cnblogs.com/lalalatianlalu/p/8450528.html

 类似资料:

相关阅读

相关文章

相关问答