当前位置: 首页 > news >正文

斜率优化dp复习笔记

P3648 [APIO2014] 序列分割

将序列分割成 \(k+1\) 个部分,每个部分的元素 \(\geq 1\),然后假设一个块你要分成两个块,代价为分成后两个块里面的元素和的乘积,问你怎么才能使代价最大,并输出方案(SPJ)。

题目分析

注意到顺序是无关紧要的:

若一个块 \(sum\) 要从 \(i,j\) 这里下手(分成三段的和 \(a,b,c\)),顺序所导致的有:

  • 先从 \(i\) 砍,代价为 \(a(b+c)+bc=ab+ac+bc\)
  • 先从 \(j\) 砍,代价为 \((a+b)c+ab=ab+ac+bc\)

两者相等,顺序无用。

故设 \(f_{i,j}\) 表示前 \(i\) 个部分切 \(j\) 次,那么有:

\[f_{i,j}=\max_{l\in[0,i-1]} f_{l,j-1}+sum_l\times(sum_i-sum_l) \]

顺序无关,所以我先在 \(i\) 切,然后再切前面的。

考虑斜率优化,对于 \(j<l\)\(j\)\(l\) 更优,并设 \(f_{x,j-1}=f_x\)

有:

\[f_j+sum_isum_j-sum_j^2>f_l+sum_isum_l-sum_l^2 \Rightarrow \frac{(f_j-sum_j^2)-(sum_l-sum_l^2)}{-sum_j-(-sum_l)}>sum_i \]

那么点集就是 \((-sum_x,f_x-sum_x^2)\)

那么对于当前点 \(i\),所有斜率 \(\leq sum_i\) 的都不可行。

然后队头就是最优决策点,为什么呢?因为对于 \(j<l\) 满足即可,显然是第一个。

也就是直接去维护斜率递增。

现在要把 \(i\) 也添加进来。那么我们维护斜率递增即可。

代码

时间复杂度 \(\mathcal{O}(nk)\),代码如下:

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <deque>
#define int long long
#define N 100005
#define K 205
using namespace std;
int pre[N][K],a[N],sum[N],f[N],g[N];
int x(int id) {return -sum[id];}
int y(int id) {return g[id] - sum[id] * sum[id];}
double slope(int fir,int sec) {if (x(fir) == x(sec)) return -1e18;return 1.0 * (y(fir) - y(sec)) / (1.0 * (x(fir) - x(sec)));
}
int q[N],head,tail;
signed main(){int n,k;cin >> n >> k;// k ++;for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]),sum[i] = sum[i - 1] + a[i];// for (int i = 0;i <= n;i ++)//     for (int j = 0;j <= n;j ++) f[i][j] = -1e18;// f[0][0] = 0;// for (int i = 1;i <= n;i ++)//     for (int j = 1;j <= min(i,k);j ++)//         for (int t = 0;t < i;t ++)//             if (f[t][j - 1] + sum[t] * (sum[i] - sum[t]) > f[i][j])//                 f[i][j] = f[t][j - 1] + sum[t] * (sum[i] - sum[t]),pre[i][j] = t;// printf("%lld\n",f[n][k]);// int now = n;// for (int j = k;j > 1;j --) printf("%lld ",pre[now][j]),now = pre[now][j];for (int t = 1;t <= k;t ++) {for (int i = 1;i <= n;i ++) g[i] = f[i];tail = 0;head = 1;// q[++tail] = 0;for (int i = 1;i <= n;i ++) {while(tail > head && slope(q[head],q[head + 1]) <= sum[i]) head ++;f[i] = 0;if (head <= tail) {pre[i][t] = q[head];f[i] = g[q[head]] + sum[q[head]] * (sum[i] - sum[q[head]]);}while(tail > head && slope(q[tail - 1],q[tail]) >= slope(q[tail],i)) tail --;q[++tail] = i;}}printf("%lld\n",f[n]);int now = n;for (int j = k;j >= 1;j --) printf("%lld ",pre[now][j]),now = pre[now][j];return 0;
}
http://www.hskmm.com/?act=detail&tid=24750

相关文章:

  • 掌握形式验证,护航芯片安全
  • 数位DP
  • 2025橡胶软接头厂家最新企业品牌推荐排行榜,法兰橡胶软接头,可曲挠,挠性,KXT,耐油,EPDM,耐腐蚀,三元乙丙橡胶软接头,橡胶柔性软接头公司推荐!
  • 整体二分笔记
  • 详细介绍:性能优化 - 案例篇:缓存_Guava#LoadingCache设计
  • 2025年X射线管厂家最新企业品牌推荐排行榜,工业用金属陶瓷,波长色散荧光分析,应力衍射分析,管板角焊缝,轮胎检测,辐照,固定阳极波纹陶瓷,测厚,食品检测 X 射线管公司推荐
  • AtCoder Beginner Contest 400
  • P14134 题解——随机化太帅了
  • 2025 年北京档案存放公司 升职猫档案服务平台:16 年老牌机构的合规服务与高效解决方案解析
  • 2025电容厂家最新品牌推荐排行榜白皮书,固态,高压,牛角,安规,CBB,超级,红宝石电解,螺栓,超级电容推荐这十家公司!
  • bug汇总
  • 2025石材加工厂家最新品牌推荐排行榜:大祥工艺,业务覆盖东北,辽宁盖州,专业浮雕雕刻高级技师
  • centos7升级降级内核 centos升级降级内核 centos升级内核 centos降级内核
  • Photoshop 在线网页版?是的,它来了!免费使用指南
  • 基于Python+Vue开发的母婴商城管理系统源码+运行步骤
  • 2025防火隔断品牌最新推荐排行榜:甲级防火玻璃隔断厂家深度解析,精选优质品牌助力采购决策!
  • 机器学习Day5-模型诊断 - 详解
  • 这些行业软件你用过哪个
  • 提供远程服务
  • 分享一些软件资讯
  • 2025美缝剂源头厂家最新推荐权威排行榜:深度解析五大品牌实力与选购指南
  • 2025数控铣床厂家最新企业品牌推荐排行榜, 双头数控铣床,双面数控铣床,龙门数控铣床,双侧数控铣床推荐这十家公司!
  • 2025最新推荐点胶机源头厂家权威排行榜:涵盖自动点胶机,果冻胶,无痕内衣,热熔胶类设备,助力企业精准挑选优质厂家
  • 前端开源JavaScrip库 - 详解
  • Probabilistic method小记
  • 数据生成方法初步调研
  • Elastic Stack 9.1.4 发布:重要安全更新与功能优化
  • 2025钛白粉源头厂家最新推荐排行榜:覆盖广东珠三角东莞华南深圳长三角地区的优质供应商解析
  • 完整教程:图论回溯
  • 用 Whisper 打破沉默:AI 语音技术如何重塑无障碍沟通方式? - 指南