[数据结构与算法]【牛客网】KY139 毕业bg

关于贪心的使用————每个阶段的最优状态都是由上一个阶段的最优状态得到的，那么该问题的状态和阶段是什么呢？现在来看关于阶段的定义，所谓阶段是指随着问题的解决，在同一个时刻可能会得到的不同状态的集合。我们可以把时间作为划分阶段的尺度，那么就是第 i 小时，就是第i阶段。因为本题要求最大快乐度，那么状态的对象一定是最大快乐度，既然阶段是时间，那么怎么定义才能让一个阶段包含多个不同状态的集合，那就是参加的不同活动的集合所带来的最大快乐度，对于本题，在一个给定的时间 i 可能一个人参加了活动1，但他同样能通过参加活动2来获得同样的快乐度。现在考虑，能不能符合————“每个阶段的最优状态都是由上一个阶段的最优状态得到”？显然是不能的，例如上一个阶段，也就是第i小时的最优状态，必定是参加了某几个活动而获得的最大快乐度。而来到了第i+1小时，现在又新增了能参加的活动，可是若该活动的开始时间与之前的活动冲突，但其提供的最大快乐度又大于之前的状态，明显，上一个阶段的最优状态并不能得到现阶段的最优解

现在，再来看动态规划，每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到放到这一道题怎么理解呢，因为前一阶段所参加了的活动可能正好与更好的活动冲突，我们可能需要跟之前的阶段，那个时候的状态能与现在这个更好的活动正好分隔开来，而之前的这个阶段的状态也一定是通过某种方法得到的，我们可以不用关心他又是怎么得来的，所以本题是符合动态规划的定义的！！因此我们定义dp[j]为j时刻所获得的最大快乐度，通过遍历所有活动，在遍历所有时间来转移所要的状态。在动态规划中又是背包的形式，状态转移方程就是，

dp[j] = Max(dp[j - bg[i].time] + bg[i].joy,dp[j]) 其中j>=bg[i].time

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 30 + 10;

struct BG{
    int happy;
    int last;
    int time;
    bool operator<(const BG b) const{
        return time < b.time;
    }
};

BG bg[N];
int dp[N];

int main(){
    int n;
    while(scanf("%d", &n) != EOF && n > 0){
        for(int i = 0; i < n; i++){
            scanf("%d%d%d", &bg[i].happy, &bg[i].last, &bg[i].time);
        }
        //要把每个活动最晚结束时间sort一下，不然不能保证某一阶段得到的是最优状态
        sort(bg, bg + n);
        int maximum = 0;
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++){
            for(int j = bg[i].time; j >= bg[i].last; j--){
                dp[j] = max(dp[j], dp[j - bg[i].last] + bg[i].happy);
                maximum = max(maximum, dp[j]);
            }
        }
        printf("%d\n", maximum);
    }
    return 0;
}