bzoj [POI2015]Myjnie
[POI2015]Myjnie
Time Limit: 40 Sec Memory Limit: 256 MBSec Special Judge
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],ci
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
Sample Output
43
5 5 13 13 20 20 13
这个区间dp有点东西。。。
离散化一下
f[l][r][t] 表示完全属于区间的人中最小值刚好是t的最优贡献。
g[l][r][t] 表示完全属于区间的人中最小值大于等于t的最优贡献。
然后你的转移就成了枚举最小值是哪个店。
f[l][r][t]=max(g[l][i-1][t]+g[i+1][r][t]+cost(i))
然而这个cost(i)有点尴尬。。。你可能还有有个预处理h[i][j]表示在处理当前这个dp区间的情况下,包含i这个位置的人且在最小值为j的情况下能给钱的人有多少个。。。
写吧~
1 mol 乱七八糟的错误。。。。。调一万年啊。。。。
```c++
include<bits/stdc++.h>
using namespace std;
const int maxm = 4004;
struct lpl{
int a, b, c;
}ini[maxm];
struct lpd{
int g, f, pos;
}dp[55][55][maxm];
int n, m, k, ans[55], pl[maxm], nam[maxm], mark[500005], h[55][maxm];
inline bool cmp(lpl A, lpl B) {return A.b == B.b ? A.a < B.a : A.b < B.b;}
inline void putit()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i) scanf("%d%d%d", &ini[i].a, &ini[i].b, &ini[i].c), pl[i] = ini[i].c;
sort(ini + 1, ini + m + 1, cmp);
sort(pl + 1, pl + m + 1); k = 0;
for(int i = 1; i <= m; ++i)
if(pl[i] != pl[i - 1]){
k++; nam[k] = pl[i]; mark[pl[i]] = k;
}
for(int i = 1; i <= m; ++i) ini[i].c = mark[ini[i].c];
}
inline void workk()
{
for(int l = n; l >= 1; --l)
for(int r = l; r <= n; ++r){
for(int i = l; i <= r; ++i)
for(int j = 1; j <= k; ++j)
h[i][j] = 0;
for(int i = 1; i <= m && ini[i].b <= r; ++i){
if(ini[i].a < l) continue;
for(int j = ini[i].a; j <= ini[i].b; ++j) h[j][ini[i].c]++;
}
for(int i = l; i <= r; ++i)
for(int j = k - 1; j >= 1; --j)
h[i][j] += h[i][j + 1];
for(int i = l; i <= r; ++i)
for(int j = k; j >= 1; --j){
int tmp = dp[l][i - 1][j].g + dp[i + 1][r][j].g + h[i][j] * nam[j];
if(dp[l][r][j].f < tmp){
dp[l][r][j].f = tmp; dp[l][r][j].pos = i;
}
dp[l][r][j].g = max(dp[l][r][j].f, dp[l][r][j + 1].g);
}
}
}
void dfs(int l, int r, int t)
{
if(l > r) return;
if(dp[l][r][t].g == 0){
for(int i = l; i <= r; ++i) ans[i] = nam[t];
return;
}
for(int i = t; i <= k; ++i){
if(dp[l][r][t].g == dp[l][r][i].f){
int now = dp[l][r][i].pos;
ans[now] = nam[i];
dfs(l, now - 1, i); dfs(now + 1, r, i);
break;
}
}
}
inline void print()
{
printf("%d\n", dp[1][n][1].g);
dfs(1, n, 1);
for(int i = 1; i <= n; ++i) printf("%d ", ans[i]);
}
int main()
{
putit();
workk();
print();
return 0;
}
最新文章
- 【svn】在提交文件是报错:previous operation has not finished;run &#39;cleanup&#39; if it was interrupted
- html热力图的操作(点击图片的不同位置操作不同的事件)适合说明文档
- java中的运算符
- LINQ的Union方法
- arcgis批量处理mxd定义服务中的路径
- pycharm 中 pep8 检查开启.
- GCD线程间通信
- 如何让你的Python代码更加pythonic ?
- Java应用的优秀管理工具Maven的下载安装及配置
- oracle 创建索引思考(转)
- DOM4J 读取XML配置文件进行数据库连接
- 使用javascript oop开发滑动(slide) 菜单控件
- HTTP协议--简析
- 在bmp上添加字符
- iOS开发之自定义UITableView的cell
- 二叉树、栈、队列、链表的Java代码实现
- 3D模型展示以及体积、表面积计算
- Git之(三)辅助命令
- Android Jetpack 组建介绍(一)——Lifecycler
- 第一周学习总结-Java
热门文章
- 二维码相关---java生成二维码名片,而且自己主动保存到手机通讯录中...
- ajax跨域请求,状态码200,F12控制台报错
- 使用腾讯地图请求来源未被授权, 此次请求来源域名/ip:servicewechat.com
- go中字符类型的使用小结
- 自定义checkbox(对勾)和radio样式
- mysql数据库的水平分表与垂直分表实例讲解
- jQuery JCrop插件的使用详解
- ubuntu oracle数据库18c安装
- LC: 404.左叶子节点
- 匹配Luhn算法:可用于检测银行卡卡号