首页 > 代码库 > BZOJ 2436 Noi嘉年华（优化DP）
BZOJ 2436 Noi嘉年华（优化DP）
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2436
题意：有一些活动，起始时间持续时间已知。有两个场地。每个活动最多只能在一个场地举行，且两个场地同一时间不能都举行活动。但是同一场地同一时间可以举行多个活动。要求的是两个场地中活动数目少的场地的活动数目的最大值S。再输出某个活动必须被安排时的S值。
思路:我直接粘贴原思路了。
区间离散化，设A={嘉年华1的活动}, B={嘉年华2的活动}，C={未安排的活动}。
设num[i][j]为包含在区间[i,j]中的区间个数；
pre[i][j]为在区间[0,i]中放入j个区间到B后，最多能放入A的个数；
suf[i][j]为在区间[i, +∞)中放入j个区间到B后，最多能放入A的个数。
那么第一问答案为：max(min(i,suf[0][i]))。
int pre[N][N],suf[N][N],g[N][N],L[N],R[N];int p[N],n,num[N][N],m;void DP(){ int i,j,k; FOR0(i,N) FOR0(j,N) pre[i][j]=suf[i][j]=g[i][j]=-INF; pre[0][0]=suf[m-1][0]=0; FOR0(i,m) { for(j=0;j<=n;j++) if(pre[i][j]>=0) { upMax(pre[i][pre[i][j]],j); } for(j=n-1;j>=0;j--) upMax(pre[i][j],pre[i][j+1]); for(j=0;j<=n+1;j++) for(k=i+1;k<m;k++) if(pre[i][j]>=0) { upMax(pre[k][pre[i][j]],j+num[i][k]); } } for(i=m-1;i>=0;i--) { for(j=0;j<=n+1;j++) if(suf[i][j]>=0) { upMax(suf[i][suf[i][j]],j); } for(j=n-1;j>=0;j--) upMax(suf[i][j],suf[i][j+1]); for(j=0;j<=n;j++) for(k=i-1;k>=0;k--) if(suf[i][j]>=0) { upMax(suf[k][suf[i][j]],j+num[k][i]); } } int x,y; FOR0(i,m) FOR0(j,m) { y=n; for(x=0;x<=n;x++) { while(y>=0&&x+y>num[i][j]+pre[i][x]+suf[j][y]) y--; if(y>=0) upMax(g[i][j],x+y); } } int ans=0; for(i=0;i<=n;i++) upMax(ans,min(i,suf[0][i])); PR(ans); FOR0(i,n) { ans=0; for(j=0;j<=L[i];j++) for(k=R[i];k<m;k++) { upMax(ans,g[j][k]); } PR(ans); }}int main(){ RD(n); int i,j; FOR0(i,n) { RD(L[i],R[i]); R[i]=R[i]+L[i]; p[m++]=L[i]; p[m++]=R[i]; } sort(p,p+m); m=unique(p,p+m)-p; FOR0(i,n) { L[i]=lower_bound(p,p+m,L[i])-p; R[i]=lower_bound(p,p+m,R[i])-p; } FOR0(i,m) { FOR0(j,n) if(L[j]>=i) num[i][R[j]]++; for(j=i+1;j<m;j++) num[i][j]+=num[i][j-1]; } DP();}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。