【BZOJ4380】[POI2015]Myjnie 区间DP
2024-08-28 03:39:24
【BZOJ4380】[POI2015]Myjnie
Description
有n家洗车店从左往右排成一排,每家店都有一个正整数价格p[i]。
有m个人要来消费,第i个人会驶过第a[i]个开始一直到第b[i]个洗车店,且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于c[i],那么这个人就不洗车了。
请给每家店指定一个价格,使得所有人花的钱的总和最大。
Input
第一行包含两个正整数n,m(1<=n<=50,1<=m<=4000)。
接下来m行,每行包含三个正整数a[i],b[i],c[i](1<=a[i]<=b[i]<=n,1<=c[i]<=500000)
Output
第一行输出一个正整数,即消费总额的最大值。
第二行输出n个正整数,依次表示每家洗车店的价格p[i],要求1<=p[i]<=500000。
若有多组最优解,输出任意一组。
Sample Input
7 5
1 4 7
3 7 13
5 6 20
6 7 1
1 2 5
1 4 7
3 7 13
5 6 20
6 7 1
1 2 5
Sample Output
43
5 5 13 13 20 20 13
5 5 13 13 20 20 13
题解:先离散化,然后DP:令f[i][j][k]表示在[i,j]中最小值为k的最大收益。然后转移时枚举[i,j]中的最小值l,然后用(f[i][l-1][k..m]+f[l+1][j][k..m]+所有经过l的顾客贡献)更新f[i][j][k]。那么如何计算所有经过l的顾客的贡献呢?我们在枚举到i和j时,先预处理出g[i][k]表示在当前区间中,经过i且限制条件>=k的顾客的数量。就容易转移了。
输出方案时对于DP的每个地方都维护个pre指针即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,M;
int f[55][55][4010],ref[4010],s[55][55][4010],g[55][4010],gp[55][55][4010],sp[55][55][4010],v[55];
struct node
{
int a,b,c;
}p[4010];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
bool cmp(const node &a,const node &b) {return a.c<b.c;}
void print(int l,int r,int x)
{
if(l>r) return ;
x=sp[l][r][x];
int mid=gp[l][r][x];
v[mid]=ref[x];
print(l,mid-1,x),print(mid+1,r,x);
}
int main()
{
n=rd(),m=rd();
int i,j,k,l;
for(i=1;i<=m;i++) p[i].a=rd(),p[i].b=rd(),p[i].c=rd();
sort(p+1,p+m+1,cmp);
for(i=1;i<=m;i++)
{
if(p[i].c>ref[M]) ref[++M]=p[i].c;
p[i].c=M;
}
//memset(f,-1,sizeof(f));
for(j=0;j<n;j++)
{
for(i=1;i+j<=n;i++)
{
memset(g,0,sizeof(g));
for(k=1;k<=m;k++) if(p[k].a>=i&&p[k].b<=i+j)
for(l=p[k].a;l<=p[k].b;l++) g[l][p[k].c]++;
for(l=i;l<=i+j;l++) for(k=M;k>=1;k--) g[l][k]+=g[l][k+1];
for(k=M;k>=1;k--)
{
for(l=i;l<=i+j;l++)
{
if(f[i][i+j][k]<=s[i][l-1][k]+s[l+1][i+j][k]+g[l][k]*ref[k])
{
f[i][i+j][k]=s[i][l-1][k]+s[l+1][i+j][k]+g[l][k]*ref[k];
gp[i][i+j][k]=l;
}
}
if(f[i][i+j][k]>=s[i][i+j][k+1])
s[i][i+j][k]=f[i][i+j][k],sp[i][i+j][k]=k;
else
s[i][i+j][k]=s[i][i+j][k+1],sp[i][i+j][k]=sp[i][i+j][k+1];
}
}
}
printf("%d\n",s[1][n][1]);
print(1,n,1);
for(i=1;i<=n;i++) printf("%d%c",v[i],i==n?'\n':' ');
return 0;
}
最新文章
- 允许Sublime编辑器在Ubuntu上输入中文
- VerifyCodeUtil.java
- How to Make Terrains in Tiled Map Editor
- Kefa and Park
- centos 连不上网
- 洛谷P1529 回家 Bessie Come Home
- js添加onclick函数
- @angular/cli (angular脚手架) 如何降级
- Qt代码
- SimpleVisitorMemberType类的visitClassType解读
- CentOS7.3 搭建Openvpn
- [LuoguP1053][Noip2005]篝火晚会
- Eclipse打开.class文件
- ArchLinux 下文件描述符
- Ubuntu13.04使用Jlink和ST-Link V2烧写STM32F1x和STM32F4x
- 012-JDK可视化监控工具-jstack
- POJ2513(字典树+图的连通性判断)
- Linux安装indicator-china-weather
- 「LuoguP3389」【模板】高斯消元法
- 响应式Web设计- Viewport
热门文章
- 织梦程序中plus文件作用介绍及安全设置
- In Mind
- cascade=CascadeType.ALL的深坑
- python-创建一个本地txt文本
- js对象成员的访问
- Python 统计代码的行数,Python脚本 统计代码
- [svc]jdk1.7.0_13(系列)下载url
- [elk]elasticsearch5.0及head插件安装
- Eclipse Jetty Integration
- 推荐一个不错的plist拆解工具,untp