学步园

这是九度5月份月赛的题目，一道基础的动态规划题目，当时对动态规划理解的不够深入，这之后的2个星期时间，也在有意的学习动态规划的思想，动态规划关键在于思想，然后就是对于题目的分析，这里ac了也记录一下自己的分析过程。

题目描述：
小明每天都在开源社区上做项目，假设每天他都有很多项目可以选，其中每个项目都有一个开始时间和截止时间，假设做完每个项目后，拿到报酬都是不同的。由于小明马上就要硕士毕业了，面临着买房、买车、给女友买各种包包的鸭梨，但是他的钱包却空空如也，他需要足够的money来充实钱包。万能的网友麻烦你来帮帮小明，如何在最短时间内安排自己手中的项目才能保证赚钱最多（注意：做项目的时候，项目不能并行，即两个项目之间不能有时间重叠，但是一个项目刚结束，就可以立即做另一个项目，即项目起止时间点可以重叠）。
输入：
输入可能包含多个测试样例。
对于每个测试案例，输入的第一行是一个整数n(1<=n<=10000)：代表小明手中的项目个数。
接下来共有n行，每行有3个整数st、ed、val，分别表示项目的开始、截至时间和项目的报酬，相邻两数之间用空格隔开。
st、ed、value取值均在32位有符号整数（int）的范围内，输入数据保证所有数据的value总和也在int范围内。
输出：
对应每个测试案例，输出小明可以获得的最大报酬。
样例输入：
3
1 3 6
4 8 9
2 5 16
4
1 14 10
5 20 15
15 20 8
18 22 12
样例输出：
16
22

思路分析

这道题是典型的动态规划题目，类似与0-1背包问题，并且比0-1背包问题简单，动态规划的一般步骤是：

1. 描述最优解的结构
2. 递归定义最优解的值
3. 按自底向上的方式计算最优解的值
4. 由计算出的结果构造一个最优解

ok,我们按照步骤来，首先分析一下最优解的结构，这也是最关键的一步：

1. 将项目根据结束时间ed大小进行升序排序，消除后效性
2. 设到第i个项目的最大报酬为f[i],则最优解结构为f[i] = max{f[i - 1], task[i].val + f[j]},其中j为满足task[j].ed < task[i].st最大的一个数。

代码写起来也很简单，用for循环，并且用数组保持之前遍历的值

#include <stdio.h>
#include <stdlib.h>
 
long long int pay[10005];
 
struct task
{
    int begin, end, value;
};
 
long long int relative_max(int i, struct task *t)
{
    int j = 0;
 
    while (t[j].end <= t[i].begin) {
        j ++;
    }
    // 找到最近的一个截至时间小于指定时间的项目
    j -= 1;
    return pay[j] + t[i].value;
}
 
int compare(const void *p, const void *q)
{
    const struct task *a = p;
    const struct task *b = q;
 
    return a->end - b->end;
}
 
int main()
{
    int i, n;
    long long int cost1, cost2;
    struct task tasks[10005];
 
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i ++) {
            scanf("%d %d %d", &tasks[i].begin, &tasks[i].end, &tasks[i].value);
        }
 
        // 按照截至时间排序
        qsort(tasks, n, sizeof(tasks[0]), compare);
 
        // 典型的动态规划
        // 最优子问题解为：max(cost[i - 1], task[i].value + 结束时间小于task[i].end的最大值)
        pay[0] = tasks[0].value;
        for (i = 1; i < n; i ++) {
            cost1 = pay[i - 1];
            cost2 = relative_max(i, tasks);
            pay[i] = (cost1 >= cost2) ? cost1 : cost2;
        }
 
        printf("%lld\n", pay[n - 1]);
    }
 
    return 0;
}
 
/**************************************************************
    Problem: 1499
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:170 ms
    Memory:1040 kb
****************************************************************/