题解"/>
演讲大厅安排题解
「演讲大厅安排」题目
【问题描述】
有一个演讲大厅需要我们管理,演讲者们事先定好了需要演讲的起始时间和中止时间。我们
想让演讲大厅得到最大可能的使用。我们要接受一些预定而拒绝其他的预定,目标是使演讲
者使用大厅的时间最长。假设在某一时刻一个演讲结束,另一个演讲就可以立即开始。
【编程任务】
计算演讲大厅最大可能的使用时间。
【输入格式】
第一行为一个整数N,N<=5000,表示申请的数目。
以下N行每行包含两个整数p,k,1<=p<k<=30000,表示这个申请的起始时间和中止时间。
【输出格式】
一个整数,表示大厅最大可能的使用时间。
【输入样例】
12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20
【输出样例】
16
题解
刚开始看到这道题我是欣喜若狂的,这和前天考的「尼克的任务」(大家学DP可以搜尼克的任务)十分相似,这里读入起始结束时间,「尼克的任务」是输入开始时间和持续时间,一样的道理,但是我并没有copy,因为这是考试,而且我也忘了很多了…我开始自己寻找递推式
我很渣我在草稿纸上打了一个小时的草稿不断调试,样例都过不了,便从头开始寻找另一种方法,经同学指点——背包问题!这就是一个01背包选与不选的关系,这就好写了,简单的01背包
思路
读入——>sort排序(末尾时间)——>两层循环一维一边推——>递推式放与不放取max
代码奉上
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespacestd;
int f[30010],n,m=-1;
struct node
{int begin;int end;
}w[5010];//这里用到了结构体存储begin时间与end时间
bool cmp(const node a,const node b)
{return(a.end<b.end)||((a.end==b.end)&&(a.begin<b.begin));
}//结构体以末尾时间排序
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d%d",&w[i].begin,&w[i].end);sort(w+1,w+1+n,cmp);//sortfor (int i=1;i<=n;i++)for (intj=w[n].end;j>=w[i].end;j--)if (j>=w[i].end)f[j]=max(f[w[i].begin]+w[i].end-w[i].begin,f[j]);//递推式,放入背包与不放入背包取maxcout<<f[w[n].end];//输出
}
更多推荐
演讲大厅安排题解
发布评论