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]);} }

 

 

 

总结

以上是生活随笔为你收集整理的ZOJ 1743 Concert Hall Scheduling（DP）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。