HDU - 3480 Division(斜率优化)
发布日期:2021-10-03 15:44:48
浏览次数:1
分类:技术文章
本文共 1856 字,大约阅读时间需要 6 分钟。
题目大意:给出N个数,要求你将N个数分成K个集合,使每个集合的(最大值 - 最小值)^ 2和达到最小
解题思路:先排个序,从小打大排
设dp[i][j]为前i个数分成j个集合最小平方和 得到转移方程dp[i][j] = dp[k][j - 1] + (val[i] - val[k + 1]) ^ 2 val[i]为第i个数的值 设l > k,且点l比点k优 则dp[k][j - 1] + (val[i] - val[k + 1]) ^ 2 >= dp[l][j - 1] + (val[i] - val[l + 1]) ^ 2 化简得val[i] >= (dp[l][j - 1] + val[l+ 1] ^ 2 - dp[k][j - 1] - val[k + 1] ^ 2 ) / (2 * val[l + 1] - 2 * val[k + 1]) 因为val随着i的增大而增大,所以得到斜率方程#include#include #include using namespace std;typedef long long LL;const int N = 10010;const int M = 5010;LL val[N];LL dp[M][N];int n, m;int que[N];void init() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%lld", &val[i]); sort(val + 1, val + 1 + n);}LL getUp(int l, int k, int j) { return dp[j - 1][l] + val[l + 1] * val[l + 1] - (dp[j - 1][k] + val[k + 1] * val[k + 1]);}LL getDown(int l, int k) { return 2 * (val[l + 1] - val[k + 1]);}void getDp(int i, int k, int j) { dp[j][i] = dp[j - 1][k] + (val[i] - val[k + 1]) * (val[i] - val[k + 1]);}int cas = 1;void solve() { for (int i = 1; i <= n; i++) dp[1][i] = (val[i] - val[1]) * (val[i] - val[1]); int head, tail; for (int i = 2; i <= m; i++) { head = tail = 0; que[tail++] = i - 1; for (int j = i; j <= n; j++) { while (head + 1 < tail && getUp(que[head + 1], que[head], i) <= getDown(que[head + 1], que[head]) * val[j]) head++; getDp(j, que[head], i); while (head + 1 < tail && getUp(j, que[tail - 1], i) * getDown(que[tail - 1], que[tail - 2]) <= getUp(que[tail - 1], que[tail - 2], i) * getDown(j, que[tail - 1])) tail--; que[tail++] = j; } } if (m >= n) dp[m][n] = 0; printf("Case %d: %lld\n", cas++, dp[m][n]);}int main() { int test; scanf("%d", &test); while (test--) { init(); solve(); } return 0;}
转载地址:https://blog.csdn.net/L123012013048/article/details/48949311 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月11日 07时04分59秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【面试篇】Java的代理模式-静态代理和动态代理详解
2019-04-26
【面试篇】 Java对象拷贝(对象克隆 对象复制)
2019-04-26
【Leetcode刷题篇】leetcode64 最小路径和
2019-04-26
【Leetcode刷题篇】leetcode79 单词搜索
2019-04-26
【Leetcode刷题篇】leetcode300 最长上升子序列
2019-04-26
【Leetcode刷题篇】leetcode394 字符串解码
2019-04-26
【Leetcode刷题篇】leetcode152 乘积最大数组
2019-04-26
【Leetcode刷题篇】leetcode56 合并区间
2019-04-26
【Leetcode刷题篇】leetcode210 课程表II
2019-04-26
【Leetcode刷题篇】leetcode207 课程表
2019-04-26
【Leetcode刷题篇】leetcode322 零钱兑换
2019-04-26
【Leetcode刷题篇】leetcode437 路径总和III
2019-04-26
【Leetcode刷题篇】leetcode416 分割等和子集
2019-04-26
【Leetcode刷题篇】leetcode31 下一个排列
2019-04-26
【Leetcode刷题篇】leetcode621 任务调度器
2019-04-26
【Leetcode刷题篇/面试篇】通俗易懂详解动态规划-背包问题详解
2019-04-26
【面试篇】HashMap1.7和HashMap1.8的详细区别对比
2019-04-26
【面试篇】ConcurrentHashMap1.8 扩容细节
2019-04-26
【面试篇】ConcurrentHashMap1.7和1.8详解对比
2019-04-26
HashMap的有关知识点大综述
2019-04-26