codeforces-214(Div. 2)-C. Dima and Salad+DP恰好背包花费

codeforces-214(Div. 2)-C. Dima and Salad

题意：有不同的沙拉，对应不同的颜值和卡路里，现在要求取出总颜值尽可能高的沙拉，同时要满足

解法：首先要把除法变成乘法，就是每次把读进来的b[ i ] 乘以 K;

　　　因为对于a [ i ] - b[ i ] * k有两种不同的可能(大于0和小于0)，可以放在一个以25000为中心的，大小为50000的dp数组里；

　　比如对于样例1：

　　input

　　3 2
　　10 8 1
　　2 7 1

　　output

　　18
这里我们缩小一下数据

我一开始不理解，为什么dp[j - b[i]]为什么只能在非-1的情况下更新dp[j];后来画了图就明白了；
下面ac代码：

//learnt and created at 2018/2/7

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 int n,k;

 int a[],b[];

 int dp[],mid = ;

 int main(){

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

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

    {

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

    }

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

    {

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

        b[i] = a[i] - b[i]*k;

    }

    memset(dp,-,sizeof(dp));　　　　　　　　//把dp数组初始化为-1；只把dp[25000]=0；

    dp[mid]=;

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

    {

        if(b[i]>=)

        {

            for(int j=; j>=b[i]; j--)

            {

                if(dp[j-b[i]] !=-)

                    dp[j] = max(dp[j-b[i]]+a[i],dp[j]);

            }

        }

        else

        {

            for(int j=; j<=+b[i]; j++)

            {

                if(dp[j-b[i]]!=-)

                    dp[j] =max(dp[j-b[i]]+a[i],dp[j]);

            }

        }

    }

    if(dp[mid]==)puts("-1");

    else printf("%d\n",dp[mid]);

    return ;

 }

巴特西

codeforces-214(Div. 2)-C. Dima and Salad+DP恰好背包花费

最新文章

热门文章