前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >PAT「1002 Business (35分)」

PAT「1002 Business (35分)」

作者头像
hotarugali
发布2022-03-01 15:45:15
2590
发布2022-03-01 15:45:15
举报

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 2days 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:

代码语言:javascript
复制
4
7 1 3
10 2 3
6 1 2
5 1 1

Sample Output:

代码语言:javascript
复制
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].ddlc + 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

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

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

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

代码

代码语言:javascript
复制
#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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-08-14,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
    • Description
      • Input Specification:
        • Output Specification:
          • Sample Input:
            • Sample Output:
            • 2. 题解
              • 分析
                • 代码
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档