CodeForces 106C 【DP】

题意：

n g dough m种商品？

每种有ai stuffing, 拿bi stuffing + ci dough -> di tugriks

rest c0 dough -> d0 tugriks

求最大的tugriks

思路：

dough是爸爸,

dp[i] 代表在花费 i 情况下前 j 个商品的最大。

枚举在 k g dough 下的各种收入情况，取最大；

大致分成两个部分，用ai + bi 获得的钱，剩下的dough去干嘛得到。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int dp[1010];

int m,n,cc0,dd0;

int a[15],b[15],c[15],d[15];

int main()

{

    cin>>n>>m>>cc0>>dd0;

    for(int i=0;i<m;i++)

        cin>>a[i]>>b[i]>>c[i]>>d[i];

    memset(dp,0,sizeof(dp));

    for(int i=0;i<m;i++)

    {

        for(int k=n;k>=c[i];k--)

        {

            int p=0,q=0,num=0;

            for(;p<=a[i]&&q<=k;p+=b[i],q+=c[i],num++)

            {

                int come1=num*d[i]+dp[k-num*c[i]];

                int come2=num*d[i]+(k-num*c[i])/cc0*dd0+dp[k-num*c[i]-(k-num*c[i])/cc0*cc0];

                int come3=k/cc0*dd0+dp[k-k/cc0*cc0];

                int come4=dp[k-k%cc0];

                dp[k]=max(dp[k],come1);

                dp[k]=max(dp[k],come2);

                dp[k]=max(dp[k],come3);

                dp[k]=max(dp[k],come4);

            }

        }

    }

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

    return 0;

}

巴特西

CodeForces 106C 【DP】

最新文章

热门文章