POJ - 3709 K-Anonymous Sequence(斜率优化)
发布日期:2021-10-03 15:44:47 浏览次数:1 分类:技术文章

本文共 1711 字,大约阅读时间需要 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]
化简后得到(dp[k] - sum[k] + k * val[k + 1] - dp[j] + sum[j] - j * val[j + 1]) / (val[k + 1] - val[j + 1]) <= i
因为i递增,所以得到斜率方程

#include 
#include
#include
using namespace std;const int N = 500010;typedef long long LL;LL sum[N], dp[N], val[N];int que[N];int n, m;void init() { scanf("%d%d", &n, &m); sum[0] = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &val[i]); sum[i] = sum[i - 1] + val[i]; }}LL getUp(int k, int j) { return (dp[k] - sum[k]) - (dp[j] - sum[j]) + k * val[k + 1] - j * val[j + 1];}LL getDown(int k, int j) { return val[k + 1] - val[j + 1];}void getDp(int i, int j) { dp[i] = dp[j] + sum[i] - sum[j] - (i - j) * val[j + 1];}void solve() { dp[0] = 0; int head, tail; head = tail = 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++; getDp(i, que[head]); if (i >= 2 * m - 1) { int t = i - m + 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() { int test; scanf("%d", &test); while (test--) { init(); solve(); } return 0;}

转载地址:https://blog.csdn.net/L123012013048/article/details/48948757 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:UVA - 12594 Naming Babies(斜率优化)
下一篇:POJ - 1180 Batch Scheduling(斜率优化DP)

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月15日 10时25分38秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java构造函数有什么用_java构造函数有什么用,怎么用 2019-04-21
mysql 匹配 隔开的_按空格分隔关键字并搜索MySQL数据库 2019-04-21
java factory用法_怎样使用Java实现Factory设计模式 2019-04-21
java窗口内容如何复制_求助Java窗口菜单如何实现复制粘贴剪切等功能(内附源代码)... 2019-04-21
盾神与砝码称重java_[蓝桥杯][算法提高VIP]盾神与砝码称重 2019-04-21
java输出狗的各类信息_第九章Java输入输出操作 2019-04-21
java notify怎么用_java 如何使用notify() 2019-04-21
java加载指定文件为当前文本,java:如何使用bufferedreader读取特定的行 2019-04-21
java metrics 怎么样,Java metrics 2019-04-21
在vscode中php语言配置,Visual Studio Code C / C++ 语言环境配置 2019-04-21
php怎么翻译数据库中的中文,javascript – 如何将翻译后的文本插入数据库php 2019-04-21
普朗克公式matlab,用MATLAB实现普朗克函数积分的快捷计算.pdf 2019-04-21
swoolec+%3c?php,PHP+Swoole并发编程的魅力 2019-04-21
php 404配置,phpcms如何配置404 2019-04-21
matlab wash矩阵产生,洗衣机净衣效能与衣损程度的关系分析 2019-04-21
php中如何调用sql server,php调用SQL SERVER 2008及以上版本的方法 2019-04-21
python多线程实现kmeans,3种方式实现python多线程并发处理 2019-04-21
matlab 变量不存在,matlab程序运行时提示变量未定义 2019-04-21
php编码函数 base58,1. Base58可逆加密 2019-04-21
oracle 在需要下列之一,Oracle存储过程中PLS-00103:出现符号“/”在需要下列之一时:(... 2019-04-21