题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=5501

题目大意

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

第 $i$ 道题目的初始分值为 $A_i(A_i \leq 10^{6})$ 分,之后每过一分钟这道题目的分值会减少 $B_i$分,并且保证到比赛结束时分值不会减少为负值。比如,一个人在第 $x$ 分钟结束时做出了第 $i$道题目,那么他/她可以得到 $A_i - B_i \times x$分。

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

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

思路

按照每题扣分/所需时间降序排序,然后利用背包求解。设$dp[t]$为前$t$分钟获得的最大分数,则$dp[t] = dp[t-problems[i].C] + problems[i].A - t*problems[i].B$。

AC代码

/*************************************************************************
    > File Name: 5501.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-13 二 19:33:42 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int T;
int t, n;
struct problem {
    int a, b, c;
    bool operator < (const problem &B) const {
        // return c * B.b < B.c * b;
        return c*1.0/b < B.c*1.0 / B.b; // 降序
    }
} problems[1002];

// const int INF = 0x3f3f3f3f;


void solve() {
    int dp[3005]; // 第i分钟得到的分数
    memset(dp, 0, sizeof(dp));
    sort(problems, problems+n);
    for(int i=0; i<problems[0].c; ++i) dp[i] = 0;
    dp[problems[0].c] = problems[0].a - problems[0].b*problems[0].c; // 做第一题得到的分数
    for(int i=1; i<n; ++i)
        for(int j=t; j>=problems[i].c; --j)
            dp[j] = max(dp[j], dp[j-problems[i].c]+problems[i].a-j*problems[i].b);
    cout << *max_element(dp, dp+t+1) << endl; // 返回最大那个分数
}

int main()
{
#ifdef Oj
    freopen("5501.in", "r", stdin);
#endif
    cin.sync_with_stdio(false);
    cin >> T;
    while(T--) {
        cin >> n >> t;
        for(int i=0; i<n; ++i) cin >> problems[i].a >> problems[i].b >> problems[i].c;
        solve();
    }
    return 0;
}