1. 题目

题目链接:PAT「1002 Business (35分)」

Description

As the manager of your company, you have to carefully consider, for each project, the time taken to finish it, the deadline, and the profit you can gain, in order to decide if your group should take this project. For example, given 33 projects as the following:

  • Project[1] takes 33 days, it must be finished in 33 days in order to gain 66 units of profit.
  • Project[2] takes 22 days, it must be finished in 22 days in order to gain 33 units of profit.
  • Project[3] takes 11 day only, it must be finished in 33 days in order to gain 44 units of profit.

You may take Project[1] to gain 66 units of profit. But if you take Project[2] first, then you will have 11 day left to complete Project[3] just in time, and hence gain 77 units of profit in total. Notice that once you decide to work on a project, you have to do it from beginning to the end without any interruption.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer NN (50\leq 50), and then followed by NN lines of projects, each contains three numbers PP, LL, and DD where PP is the profit, LL the lasting days of the project, and DD the deadline. It is guaranteed that LL is never more than DD, and all the numbers are non-negative integers.

Output Specification:

For each test case, output in a line the maximum profit you can gain.

Sample Input:

1
2
3
4
5
4
7 1 3
10 2 3
6 1 2
5 1 1

Sample Output:

1
18

2. 题解

分析

明显是一道 dp 题(联想下背包问题),设 f[j][i]f[j][i] 表示第 jj 天后且处理完前面 ii 个事务后,还能得到的最大 profit 。首先,需要将事务排序,按照 deadline 由小到大排序。为什么要这样做呢 ? 由于如上设置状态,因此需要按照先后顺序处理每个事务,而顺序处理需要考虑前后影响的问题。比如:假设没有排序时,最终答案的处理顺序为 ,j,a1,a2,,am,i,\cdots,j,a_1,a_2,\cdots,a_m,i,\cdots,且有 p[i].ddlp[a1].ddlp[am].ddlp[j].ddlp[i].ddl \leq p[a_1].ddl \leq \cdots \leq p[a_m].ddl \leq p[j].ddl,设处理到 jj 时的天数为 cc ,则有

  • c+p[j].lastingp[j].ddlc + p[j].lasting \leq p[j].ddl
  • c+p[j].lasting+p[a1].lastingp[a1].ddlc + p[j].lasting + p[a_1].lasting \leq p[a_1].ddl
  • \cdots
  • c+p[j].lasting+p[a1].lasting++p[am].lastingp[am].ddlc + p[j].lasting + p[a_1].lasting + \cdots + p[a_m].lasting \leq p[a_m].ddl
  • c+p[j].lasting+p[a1].lasting++p[am].lasting+p[i].lastingp[i].ddlc + p[j].lasting + p[a_1].lasting + \cdots + p[a_m].lasting + p[i].lasting \leq p[i].ddl

由于 p[i].ddlp[a1].ddlp[am].ddlp[j].ddlp[i].ddl \leq p[a_1].ddl \leq \cdots \leq p[a_m].ddl \leq p[j].ddlc+p[j].lasting+p[a1].lasting++p[am].lasting+p[i].lastingp[i].ddlc + p[j].lasting + p[a_1].lasting + \cdots + p[a_m].lasting + p[i].lasting \leq p[i].ddl,故有

  • c+p[i].lastingp[i].ddlc + p[i].lasting \leq p[i].ddl
  • c+p[i].lasting+p[a1].lastingp[i].ddlp[a1].ddlc + p[i].lasting + p[a_1].lasting \leq p[i].ddl \leq p[a_1].ddl
  • \cdots
  • c+p[i].lasting+p[a1].lasting++p[am].lastingp[i].ddlp[am].ddlc + p[i].lasting + p[a_1].lasting + \cdots + p[a_m].lasting \leq p[i].ddl \leq p[a_m].ddl
  • c+p[i].lasting+p[a1].lasting++p[am].lasting+p[j].lastingp[i].ddlp[j].ddlc + p[i].lasting + p[a_1].lasting + \cdots + p[a_m].lasting + p[j].lasting \leq p[i].ddl \leq p[j].ddl

即此时调换处理事务 iijj 的顺序,仍然可以处理事务 a1,,ama_1,\cdots,a_m,即不会影响最终总 profit 。因此,最终最好的事务处理顺序总可以转换成一个按照 ddlddl 顺序处理的顺序。由于我们总是按照数组下标顺序处理(即循环),因此,我们需要对事务按照 deadline 由小到大排序。

于是乎,我们可以列出状态转移方程:

f[j][i]={max{f[j][i+1],f[j+p[i+1].lasting][i+1]+p[i].profit} if j+p[i].lastingp[i].ddl,0i<nf[j][i]=f[j][i+1] if j+p[i].lasting>p[i].ddl,0i<n0 if i=nf[j][i] = \begin{cases} \max\{f[j][i+1], f[j+p[i+1].lasting][i+1]+p[i].profit\} & \text{ if } j+p[i].lasting \leq p[i].ddl, 0 \leq i < n \\ f[j][i] = f[j][i+1] & \text{ if } j+p[i].lasting > p[i].ddl, 0 \leq i < n \\ 0 & \text{ if } i = n \end{cases}

最终答案即为 f[0][0]f[0][0]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 55;
const int MAXM = 1e6;

typedef struct {
int profit, lasting, ddl;
}project;

bool operator < (const project &p1, const project &p2) {
return p1.ddl < p2.ddl;
}

int f[MAXM][MAXN];
project p[MAXN];

int mymax(int x, int y) { return x < y ? y : x; }

int answer(int n, int m) {
for(int i = n; i; --i) {
for(int j = m; ~j; --j) {
f[j][i-1] = f[j][i];
if(j+p[i].lasting \leq p[i].ddl) {
f[j][i-1] = mymax(f[j][i-1], f[j+p[i].lasting][i] + p[i].profit);
}
}
}
return f[0][0];
}

int main()
{
int n;
int m = 0;
scanf("%d", &n);
for(int i = 1; i \leq n; ++i) {
scanf("%d%d%d", &p[i].profit, &p[i].lasting, &p[i].ddl);
}
sort(p+1,p+n+1);
printf("%d\n", answer(n, p[n].ddl));
return 0;
}