PAT「1002 Business (35分)」

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 $3$ projects as the following:

• Project[1] takes $3$ days, it must be finished in $3$ days in order to gain $6$ units of profit.
• Project[2] takes $2$ days, it must be finished in $2$ days in order to gain $3$ units of profit.
• Project[3] takes $1$ day only, it must be finished in $3$ days in order to gain $4$ units of profit.

You may take Project[1] to gain $6$ units of profit. But if you take Project[2] first, then you will have $1$ day left to complete Project[3] just in time, and hence gain $7$ 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 $N$ ($\leq 50$), and then followed by $N$ lines of projects, each contains three numbers $P$, $L$, and $D$ where $P$ is the profit, $L$ the lasting days of the project, and $D$ the deadline. It is guaranteed that $L$ is never more than $D$, 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:

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

Sample Output:

18

2. 题解

分析

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

• $c + p[j].lasting \leq p[j].ddl$
• $c + p[j].lasting + p[a_1].lasting \leq p[a_1].ddl$
• $\cdots$
• $c + p[j].lasting + p[a_1].lasting + \cdots + p[a_m].lasting \leq p[a_m].ddl$
• $c + p[j].lasting + p[a_1].lasting + \cdots + p[a_m].lasting + p[i].lasting \leq p[i].ddl$

由于 $p[i].ddl \leq p[a_1].ddl \leq \cdots \leq p[a_m].ddl \leq p[j].ddl$ 且 $c + p[j].lasting + p[a_1].lasting + \cdots + p[a_m].lasting + p[i].lasting \leq p[i].ddl$，故有

• $c + p[i].lasting \leq p[i].ddl$
• $c + p[i].lasting + p[a_1].lasting \leq p[i].ddl \leq p[a_1].ddl$
• $\cdots$
• $c + 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[a_1].lasting + \cdots + p[a_m].lasting + p[j].lasting \leq p[i].ddl \leq p[j].ddl$

即此时调换处理事务 $i$ 和 $j$ 的顺序，仍然可以处理事务 $a_1,\cdots,a_m$，即不会影响最终总 profit 。因此，最终最好的事务处理顺序总可以转换成一个按照 $ddl$ 顺序处理的顺序。由于我们总是按照数组下标顺序处理（即循环），因此，我们需要对事务按照 deadline 由小到大排序。

于是乎，我们可以列出状态转移方程：

$$f[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]$ 。

代码

#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;
}