SCAU16年新生赛华山论剑---活动安排(dp)

系统管理员 2023-07-09 02:26 42阅读 0赞

## 题目描述 ##

Description  
IMIS4班有一群可爱的人  
为了使刚入学的新生们尽快适应大学生活，作为IMIS4班助班的DingDong希望班委能在9月份安排一些活动。  
因此班长RandB起草了n个备选活动方案，每个活动将有一个开始日期和结束日期（闭区间）。RanB希望从  
这n个活动中选择尽量多的活动。但由于同学们精力有限，被选中的活动不允许时间重叠。  
团支书太阳藤看完策划书后认为活动并不是越丰富越好，应当为每一个备选活动确定一个满意度，使得选  
出的活动满意度之和最大。  
学习委员傻傻嘿嘿食雪批听取了RandB和太阳藤的意见后，分析到如果某一项活动有很高的满意度，而紧随  
其后安排了一个低满意度的活动，将会大大影响同学们的参与热情。为此与班主任韦老师和同学们深入讨论  
后决定，要求下一次举行的活动必须比这一次的满意度高（不可以相等）。  
现在，你需要编写一份程序来确定满意度之和最大为多少？  
输入格式  
第一行输入n（1 <= n <= 1000），表示有n个备选活动  
接下来有n行，每行三个数。分别表示开始日期、结束日期和满意度  
（1 <= 开始日期 <= 结束日期 <= 30 ， 满意度为1到100的整数）

输出格式  
输出一个数，表示最大满意度之和

输入样例  
4  
1 2 2  
2 3 4  
3 4 3  
5 6 3

输出样例  
5

提示  
可以选择第1、3项活动或第1、4项活动，都满足题目要求。  
不可以选择第1、2项活动，因为时间有重叠。  
也不可以选择第1、3、4项活动，虽然时间上满足要求，但是满意度不严格递增，第3、4项满意度相同。

## 简单说下这题的做法 ##

这道题很明显是用dp来写的，那么我们如何求出在给定范围天数内获得的满意度最大呢？？  
首先为了dp方便，我们需要对数据排个序。  
先定义一个结构体数组，记录begin 、end、happy，我们按begin来对结构体数组排序。  
排序后的结构题数组是一个按b有序不下降的数组，那么对于这道题目，剩下的就是求最大上升子序列了。  
那么怎么求呢？  
其实很简单，两个for就ok了，对于这道题目的dp，我们可以假设每个dp的状态都是包含现在这个活动下的最大满意度，我们只需要求得最大满意度就好了，所以我们只需要使用打内算法，求出所有状态下的最大值即为答案。  
代码如下  
：

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    using namespace std;
    typedef struct
    {
        
        int b,e,h;
    }NODE;
    bool cmp(NODE x,NODE y)
    {
        
        return x.b<y.b;
    }
    int main()
    {
        
        int n,max1;
        cin>>n;
        int dp[1005];
        NODE a[1005];
        for(int i=1;i<=n;i++)
            cin>>a[i].b>>a[i].e>>a[i].h;
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++)
        {
        
            dp[i]=a[i].h;
            for(int j=1;j<i;j++)
            {
        
                if(a[i].b>a[j].e&&a[i].h>a[j].h)
                    {
        
                        dp[i]=max(dp[i],dp[j]+a[i].h);
                    }
                    max1=max(dp[i],max1);
            }
        }
        cout<<max1<<endl;
        return 0;
    }