HDU 5501 The Highest Mark 背包dp

The Highest Mark

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

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

Description

2045年的SD省队选拔，赛制和三十年前已是完全不同。一场比赛的比赛时间有 ttt 分钟，有 nnn 道题目。

第 iii 道题目的初始分值为 Ai(Ai≤106)A_i(A_i \leq 10^{6})A​i​​(A​i​​≤10​6​​) 分，之后每过一分钟这道题目的分值会减少 BiB_iB​i​​ 分，并且保证到比赛结束时分值不会减少为负值。比如，一个人在第 xxx 分钟结束时做出了第 iii 道题目，那么他/她可以得到 Ai−Bi∗xA_i - B_i * xA​i​​−B​i​​∗x 分。

若一名选手在第 xxx 分钟结束时做完了一道题目，则他/她可以在第 x+1x+1x+1 分钟开始时立即开始做另一道题目。

参加省队选拔的选手 dxy 具有绝佳的实力，他可以准确预测自己做每道题目所要花费的时间，做第 iii 道需要花费 Ci(Ci≤t)C_i(C_i \leq t)C​i​​(C​i​​≤t) 分钟。由于 dxy 非常神，他会做所有的题目。但是由于比赛时间有限，他可能无法做完所有的题目。他希望安排一个做题的顺序，在比赛结束之前得到尽量多的分数

Input

第一行为一个正整数 T(T≤10)T(T \leq 10)T(T≤10)，表示数据组数(n>200n>200n>200的数据不超过555组)。

对于每组数据，第一行为两个正整数 n(n≤1000)n (n \leq 1000)n(n≤1000) 和 t(t≤3000)t (t \leq 3000)t(t≤3000), 分别表示题目数量和比赛时间。接下来有 nnn 行，每行 333 个正整数依次表示 Ai,Bi,CiA_i, B_i, C_iA​i​​,B​i​​,C​i​​，即此题的初始分值、每分钟减少的分值、dxy做这道题需要花费的时间。

Output

对于每组数据输出一行一个整数，代表dxy这场比赛最多能得多少分

Sample Input

1

4 10

110 5 9

30 2 1

80 4 8

50 3 2

Sample Output

88

HINT

题意

题解：

按照性价比排序之后，跑一遍背包dp就好了，详解见：http://bestcoder.acmcoder.com/

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

struct node

{

    long long a,b,c;

};

node p[];

bool cmp(node a,node b)

{

    return a.b*b.c>b.b*a.c;

}

long long dp[];

int main()

{

    int cas;scanf("%d",&cas);

    while(cas--)

    {

        memset(dp,,sizeof(dp));

        memset(p,,sizeof(p));

        int n,t;

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

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

            scanf("%lld%lld%lld",&p[i].a,&p[i].b,&p[i].c);

        sort(p+,p++n,cmp);

        long long ans = ;

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

            for(int j=t;j>=p[i].c;j--)

                dp[j]=max(dp[j],dp[j-p[i].c]+p[i].a-p[i].b*j);

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

            ans = max(ans,dp[i]);

        cout<<ans<<endl;

    }

}