首页 > > 程序设计 > C/C++ >

2015暑假多校联合---CRB and His Birthday（01背…

2018-06-17 23:50:09来源：未知阅读 ()

题目链接

http://acm.split.hdu.edu.cn/showproblem.php?pid=5410

Problem Description

Today is CRB's birthday. His mom decided to buy many presents for her lovely son.
She went to the nearest shop with

Input

There are multiple test cases. The first line of input contains an integer

Output

For each test case, output the maximum candies she can gain.

Sample Input

100 2

10 2 1

20 1 1

Sample Output

Hint

CRB's mom buys 10 presents of first kind, and receives 2 × 10 + 1 = 21 candies.

Author

KUT（DPRK）

Source

2015 Multi-University Training Contest 10

Recommend

wange2014

题意：输入M，N，分别表示总的钱数和物品种数，接下来输入N行，每行3个数，单价、买一件送的糖数、买一次送的糖数求最多能得到多少糖？

思路：01背包，dp[i]表示i钱下能得到最多的糖数，vis[i][j]表示i钱下得到最多糖时，是否买j物品，状态转移方程dp[i]=dp[i-kind[j][0]]+kind[j][1]+(vis[i-kind[j][0]][j]==0) * kind[j][2]；

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#define eps 1e-8
#define maxn 105
#define inf 0x3f3f3f3f3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;
int dp[2005];
int vis[2005][1005];
int kind[1005][3];

int main()
{
    int T;
    int M,N;
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&M,&N);
        for(int i=0;i<N;i++)
            scanf("%d%d%d",&kind[i][0],&kind[i][1],&kind[i][2]);
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));

        for(int i=1;i<=M;i++)
        {
            int flag=-1;
            for(int j=0;j<N;j++)
            {
                if(i<kind[j][0]) continue;
                int s=dp[i-kind[j][0]]+kind[j][1];
                if(!vis[i-kind[j][0]][j]) s+=kind[j][2];
                if(dp[i]<s)
                {
                    dp[i]=s;
                    flag=j;
                }
            }
            if(flag>=0)
            {
                for(int j=0;j<N;j++)
                {
                    vis[i][j]=vis[i-kind[flag][0]][j];
                }
                vis[i][flag]++;
            }
        }
        int tmp=0;
        for(int i=1;i<=M;i++)
           tmp=max(tmp,dp[i]);
        printf("%d\n",tmp);
    }
    return 0;
}