题目地址：HDU 5410

题意：有M元钱，N种礼物，若第i种礼物买x件的话。会有Ai*x+Bi颗糖果，现给出每种礼物的单位价格、Ai值与Bi值。问最多能拿到多少颗糖果。

思路：全然背包问题。

dp[j][1]在当前物品时花钱为j的而且买过当前物品的最大值。

dp[j][0]不买当前这件物品此前花钱为j的的最大值。

每种物品的价值随Ai线性变化，可是不随B[i]线性变化。B[i]仅是在第一次挑选第i件物品是才算入，其它时候均不算入。

所以我们能够写出状态转移方程：

dp[j][0]=max(dp[j][1],dp[j][0]);

dp[j][1]=max(dp[j-q[i].w][0]+q[i].a+q[i].b,dp[j-q[i].w][1]+q[i].a);

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <sstream>

#include <algorithm>

#include <set>

#include <queue>

#include <stack>

#include <map>

#include <bitset>

#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

typedef long long  LL;

const int inf=0x3f3f3f3f;

const double pi= acos(-1.0);

const double esp=1e-7;

const int Maxn=2010;

struct node

{

    int a,b,w;

}q[Maxn];

int dp[Maxn][2];

int main()

{

    int T,n,m,i,j;

    scanf("%d",&T);

    while(T--){

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

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

            scanf("%d %d %d",&q[i].w,&q[i].a,&q[i].b);

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

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

            for(j=0;j<=m;j++){

                dp[j][0]=max(dp[j][1],dp[j][0]);

                if(j>=q[i].w)

                dp[j][1]=max(dp[j-q[i].w][0]+q[i].a+q[i].b,dp[j-q[i].w][1]+q[i].a);

            }

        }

        printf("%d\n",max(dp[m][0],dp[m][1]));

    }

    return 0;

}