BZOJ4380 : [POI2015]Myjnie
2024-10-14 20:36:43
将$c$离散化,设:
$f[i][j][k]$为区间$[i,j]$最小值为$k$的最大收益。
$g[i][j][k]$为$\max(g[i][j][k..m])$。
$h[i][j]$为对于当前DP区间,经过$i$点的,费用限制$\geq j$的人数。
然后直接DP即可,时间复杂度$O(n^3m)$。
#include<cstdio>
#include<algorithm>
const int N=52,M=4002;
int n,m,i,j,k,x,y,t,a[M],b[M],c[M],v[M],h[N][M];
char f[N][N][M];int g[N][N][M];short p[N][N][M];
inline int lower(int x){
int l=1,r=m,mid,t;
while(l<=r)if(v[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;
return t;
}
void dfs(int l,int r,int k){
if(l>r)return;
int x=f[l][r][k=p[l][r][k]];
a[x]=v[k],dfs(l,x-1,k),dfs(x+1,r,k);
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]),v[i]=c[i];
for(std::sort(v+1,v+m+1),i=1;i<=m;i++)c[i]=lower(c[i]);
for(i=n;i;i--)for(j=i;j<=n;j++){
for(k=i;k<=j;k++)for(x=1;x<=m;x++)h[k][x]=0;
for(k=1;k<=m;k++)if(i<=a[k]&&b[k]<=j)for(x=a[k];x<=b[k];x++)h[x][c[k]]++;
for(k=i;k<=j;k++)for(x=m-1;x;x--)h[k][x]+=h[k][x+1];
for(k=m;k;k--){
for(y=0,x=i;x<=j;x++){
t=g[i][x-1][k]+g[x+1][j][k]+v[k]*h[x][k];
if(t>=y)y=t,f[i][j][k]=x;
}
if(y>=g[i][j][k+1])g[i][j][k]=y,p[i][j][k]=k;
else g[i][j][k]=g[i][j][k+1],p[i][j][k]=p[i][j][k+1];
}
}
dfs(1,n,1);
for(printf("%d\n",g[1][n][1]),i=1;i<=n;i++)printf("%d ",a[i]);
return 0;
}
最新文章
- jQuery文本段落展开和折叠效果
- WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED解决方法
- C++笔试题(转)
- PowerDesigner概念数据模型 CDM
- CCClippingNode bug
- Eclipse创建Maven Web项目 + 测试覆盖率 + 常见问题(2015.07.14——湛耀)
- javascript ";非法值";检验.
- js控制浏览器后退
- Linux 小记 — 网络管理
- FusionCharts 2D柱状图和折线图的组合图调试错误
- vue安装遇到vue不是内部变量
- 简单尝试利用维控LeviStudioU的一栈缓冲区溢出漏洞
- luogu3242 接水果 (整体二分+树状数组)
- 洛谷P1605 迷宫 (DFS)
- delete attempted to return null from a method with a primitive return type (int)
- 【转】Linux 如何通过命令仅获取IP地址
- POJ1644状态转移的思想——排列组合
- java 路径的问题
- 转帖 IBM要推POWER9,来了解一下POWER处理器的前世今生
- CVPR2018资源汇总
热门文章
- SQL 映射的 XML 文件
- SQL学习笔记----更改SQL默认的端口号
- c++11中的static
- C# 设计模式 提高可维护性的几点原则
- 数据库递归查询-CTE
- struts标签<;logic:iterate>;的用法
- CentOS-6.5安装配置Tengine
- Jenkins搭建
- IBM AppScan 安全扫描:支持弱 SSL 密码套件 分类: 数据安全 2014-06-28 11:34 1844人阅读 评论(0) 收藏
- .NET Nancy 详解(四) Self Host