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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.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_[蓝桥杯][算法提高VIP]盾神与砝码称重
2019-04-21
java输出狗的各类信息_第九章Java输入输出操作
2019-04-21
java notify怎么用_java 如何使用notify()
2019-04-21
java metrics 怎么样,Java metrics
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
python多线程实现kmeans,3种方式实现python多线程并发处理
2019-04-21
matlab 变量不存在,matlab程序运行时提示变量未定义
2019-04-21
php编码函数 base58,1. Base58可逆加密
2019-04-21