将$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;
}

  

最新文章

  1. jQuery文本段落展开和折叠效果
  2. WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED解决方法
  3. C++笔试题(转)
  4. PowerDesigner概念数据模型 CDM
  5. CCClippingNode bug
  6. Eclipse创建Maven Web项目 + 测试覆盖率 + 常见问题(2015.07.14——湛耀)
  7. javascript &quot;非法值&quot;检验.
  8. js控制浏览器后退
  9. Linux 小记 — 网络管理
  10. FusionCharts 2D柱状图和折线图的组合图调试错误
  11. vue安装遇到vue不是内部变量
  12. 简单尝试利用维控LeviStudioU的一栈缓冲区溢出漏洞
  13. luogu3242 接水果 (整体二分+树状数组)
  14. 洛谷P1605 迷宫 (DFS)
  15. delete attempted to return null from a method with a primitive return type (int)
  16. 【转】Linux 如何通过命令仅获取IP地址
  17. POJ1644状态转移的思想——排列组合
  18. java 路径的问题
  19. 转帖 IBM要推POWER9,来了解一下POWER处理器的前世今生
  20. CVPR2018资源汇总

热门文章

  1. SQL 映射的 XML 文件
  2. SQL学习笔记----更改SQL默认的端口号
  3. c++11中的static
  4. C# 设计模式 提高可维护性的几点原则
  5. 数据库递归查询-CTE
  6. struts标签&lt;logic:iterate&gt;的用法
  7. CentOS-6.5安装配置Tengine
  8. Jenkins搭建
  9. IBM AppScan 安全扫描:支持弱 SSL 密码套件 分类: 数据安全 2014-06-28 11:34 1844人阅读 评论(0) 收藏
  10. .NET Nancy 详解(四) Self Host