cogs 1377. [NOI2011] NOI嘉年华 (dp
2024-08-29 10:48:01
题意:给你n个活动的起止时间,要你从中选一些活动在2个会场安排(不能有两个活动在两个会场同时进行),使活动较少的会场活动数最大,以及在某个活动必须选择的前提下,求该答案。
思路:由于n很小,时间很大,先将时间离散化,num[l][r]表示全部在[l,r]内的活动个数,pre[i][j]表示前i的时间内给一边j个另一边最多有几个,则用1<=k<=i更新pre[i][j]=max(pre[k][j]+num[k][j],pre[k][j-num[k][i]]),第一问答案是min(pre[time][k],k)中的最大值
第二问,相当于一段区间s[i],t[i]必选,对于l<=s[i],r>=t[i],算出f[l][r] = min(x+y,pre[l][x]+num[l][r]+suf[r][y])中的最大值,x+y关于x,y单增,pre[l][x]+num[l][r]+suf[r][y]关于x,y单减,x,y不会同时变大或变小,所以从小到大枚举x时,y从大到小...
#include<bits/stdc++.h>
#define fo(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout);
using namespace std;
inline int read(){
char ch=getchar();
int res=,f=;
while(!isdigit(ch))f^=(ch=='-'),ch=getchar();
while(isdigit(ch))res=(res+(res<<)<<)+(ch^),ch=getchar();
return res*f;
}
const int N=;
int n,s[N],t[N],a[N],cnt,pre[N][N],suf[N][N],f[N][N],num[N][N];
inline void chemx(int &a,int b){
a=a>b?a:b;
}
inline void chemn(int &a,int b){
a=a>b?b:a;
}
#define calc(a,b) (min((a+b),(pre[l][a]+num[l][r]+suf[r][b])))
int main(){
fo("noi2011_show");
n=read();
for(int i=;i<=n;i++)s[i]=read(),a[++cnt]=s[i],t[i]=read()+s[i],a[++cnt]=t[i];
sort(a+,a+cnt+);
cnt=unique(a+,a+cnt+)-a-;
for(int i=;i<=n;i++){
s[i]=lower_bound(a+,a+cnt+,s[i])-a;
t[i]=lower_bound(a+,a+cnt+,t[i])-a;
for(int l=;l<=s[i];l++)
for(int r=t[i];r<=cnt;r++)num[l][r]++;
}
for(int i=;i<=cnt;i++)
for(int j=;j<=n;j++)pre[i][j]=suf[i][j]=-1e9;
for(int i=;i<=cnt;i++)
for(int j=;j<=num[][i];j++)
for(int k=;k<=i;k++){
chemx(pre[i][j],pre[k][j]+num[k][i]);
if(j>=num[k][i])chemx(pre[i][j],pre[k][j-num[k][i]]);
}
for(int i=cnt;i;i--)
for(int j=;j<=num[i][cnt];j++)
for(int k=cnt;k>=i;k--){
chemx(suf[i][j],suf[k][j]+num[i][k]);
if(j>=num[i][k])chemx(suf[i][j],max(suf[k][j]+num[i][k],suf[k][j-num[i][k]]));
}
for(int l=;l<=cnt;l++){
for(int r=l;r<=cnt;r++){
for(int x=,y=num[r][cnt];x<=num[][l];x++){
while(y&&calc(x,y)<=calc(x,y-))y--;
chemx(f[l][r],calc(x,y));
}
}
}
int ans=;
for(int i=;i<=cnt;i++)for(int j=;j<=num[][i];j++)chemx(ans,min(pre[i][j],j));
cout<<ans<<'\n';
for(int i=;i<=n;i++){
int res=;
for(int l=s[i];l;l--)
for(int r=t[i];r<=cnt;r++)
chemx(res,f[l][r]);
cout<<res<<'\n';
}
}
最新文章
- 【JAVA多线程问题之死锁】
- 深度学习入门教程UFLDL学习实验笔记二:使用向量化对MNIST数据集做稀疏自编码
- 3月3日(3) Binary Tree Preorder Traversal
- HDU4614 Vases and Flowers 二分+线段树
- Php环境下载(PHPNow)安装
- loadrunner:参数类型及其取值机制
- openMP编程(上篇)之指令和锁
- PAT乙级-1056. 组合数的和(15)
- MySQL 笔记整理(3) --事务隔离,为什么你改了我还看不见?
- jdk 生成证书
- 数据类型+内置方法 python学习第六天
- ag 命令的帮助文档
- 记一次包含iframe的需要滚动的元素不能滚动到底部的问题
- internal in C#
- Linux中找出占用内存最多的前N个进程
- 浅谈fhq_treap
- mysql 闪回测试
- CentOS6启动流程(含详细流程图)
- Firebird 表字段查询
- 状态开关(ToggleButton)