首页 > 代码库 > ZOJ 1743 Concert Hall Scheduling（DP）
ZOJ 1743 Concert Hall Scheduling（DP）
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=743
题意：有两个音乐厅出租。给出n个租客，每个租客有个租的时间段[L,R]，以及租费。任意时候音乐厅只能租给最多一个租客。问如何选择租给哪些租客使得赚的钱最多？
思路：f[i][j]表示第一个音乐厅到时刻i、第二个到时刻j，可以获得的最大值。
struct node{ int x,y,w; int operator<(const node &a) const { return y<a.y; }};int f[N][N],n;node a[N];int main(){ Rush(n) { if(!n) break; int i; FOR1(i,n) RD(a[i].x,a[i].y,a[i].w); sort(a+1,a+n+1); clr(f,0); int j,k; FOR1(i,n) { for(j=a[i-1].y+1;j<=a[i].y;j++) for(k=0;k<=a[i].y;k++) { f[j][k]=f[j-1][k]; f[k][j]=f[k][j-1]; } for(j=a[i].y;j>=0;j--) { upMax(f[j][a[i].y],f[j][a[i].x-1]+a[i].w); upMax(f[a[i].y][j],f[a[i].x-1][j]+a[i].w); } } PR(f[a[n].y][a[n].y]); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。