HDU - 3045 Picnic Cows(斜率优化)
发布日期:2021-10-03 15:44:46
浏览次数:2
分类:技术文章
本文共 1720 字,大约阅读时间需要 5 分钟。
题目大意:给你N个整数,现在要求你将这些整数分块,使得每块的数的数量大于等于k,每块的价值为,这个块里面的所有数 - 这个块里面的最小的数
每块的价值总和的最小值解题思路:先排个序,从小到大排,这样能使价值达到最小
设dp[i]为前i个数的划分完后的总价值 得到转移方程dp[i] = dp[j] + sum[i] - sum[j] - (i - j) * val[j + 1] sum[i]指的是前i个数的和,val[i]指第i个数的值 现在假设k > j且k点比j点优 则 dp[j] + sum[i] - sum[j] - (i - j) * val[j + 1] >= dp[k] + sum[i] - sum[k] - (i - k) * val[k + 1] 化简得到 i >= (dp[k] - sum[k] + k * val[k + 1] - dp[j] + sum[j] - j * val[j + 1]) / (val[l + 1] - val[k + 1]) 因为i递增,所以得到斜率方程#include#include #include using namespace std;const int N = 400100;typedef long long LL;int n, T;int que[N];LL sum[N], val[N], dp[N];void init() { for (int i = 1; i <= n; i++) scanf("%lld", &val[i]); sort(val + 1, val + 1 + n); sum[0] = 0; for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + val[i];}LL getUp(int j, int k) { return dp[j] - sum[j] + j * val[j + 1] - (dp[k] - sum[k] + k * val[k + 1]);}LL getDown(int j, int k) { return val[j + 1] - val[k + 1];}void solve() { int head, tail; head = tail = 0; dp[0] = 0; que[tail++] = 0; for (int i = 1; i <= n; i++) { while (head + 1 < tail && getUp(que[head + 1], que[head]) <= getDown(que[head + 1], que[head]) * i) head++; dp[i] = dp[que[head]] + sum[i] - sum[que[head]] - (i - que[head]) * val[que[head] + 1]; if (i >= 2 * T - 1) { int t = i - T + 1; while (head + 1 < tail && getUp(t, que[tail - 1]) * getDown(que[tail - 1], que[tail - 2]) <= getUp(que[tail - 1], que[tail - 2]) * getDown(t, que[tail - 1])) tail--; que[tail++] = t; } } printf("%lld\n", dp[n]);}int main() { while (scanf("%d%d", &n, &T) != EOF) { init(); solve(); } return 0;}
转载地址:https://blog.csdn.net/L123012013048/article/details/48948231 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月31日 09时21分26秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
多路IO复用模型 select epoll 等
2019-04-27
Linux Epoll介绍和程序实例
2019-04-27
output_buffering详细介绍
2019-04-27
php缓冲 output_buffering和ob_start
2019-04-27
php error_reporting 详解
2019-04-27
剖析PHP中的输出缓冲
2019-04-27
HTTP响应头不缓存
2019-04-27
PHP安装扩展mcrypt以及相关依赖项 【PHP安装PECL扩展的方法】
2019-04-27
Javascript到PHP加密通讯的简单实现
2019-04-27
德国SNS交友/视频网站Poppen.de的技术架构分享
2019-04-27
UNIX环境编程
2019-04-27
一笔画问题【数据结构-图论】
2019-04-27
红黑树
2019-04-27
安装多个gcc
2019-04-27
Linux0.01内核根目录Makefile注释
2019-04-27
【CSDN2012年度博客之星】需要您的一票,感谢大家的支持
2019-04-27
PHP对于浮点型的数据需要用不同的方法去解决
2019-04-27
Tokyo Cabinet 安装
2019-04-27
Flink在美团的应用与实践听课笔记
2019-04-27
Java多线程的11种创建方式以及纠正网上流传很久的一个谬误
2019-04-27