HDU 2829 Lawrence (斜率DP)

时间:2022-10-31 21:56:12

斜率DP

设dp[i][j]表示前i点,炸掉j条边的最小值。j<i

dp[i][j]=min{dp[k][j-1]+cost[k+1][i]}

又由得出cost[1][i]=cost[1][k]+cost[k+1][i]+sum[k]*(sum[i]-sum[k])

cost[k+1][i]=cost[1][i]-cost[1][k]-sum[k]*(sum[i]-sum[k])

代入DP方程

可以得出 y=dp[k][j-1]-cost[1][k]+sum[k]^2

x=sum[k].

斜率sum[i]

const maxn=;
var n,m,i,j,h,t:longint;
a,sum,cost,q:array[..maxn*] of int64;
f:array[..maxn,..maxn] of int64;
function kx(x,y:int64):int64;
begin
exit(sum[x]-sum[y]);
end;
function ky(x,y:int64):int64;
begin
exit((f[x,j-]-cost[x]+sum[x]*sum[x])-(f[y,j-]-cost[y]+sum[y]*sum[y]))
end;
begin
readln(n,m);
for i:= to n do read(a[i]);
for i:= to n do sum[i]:=sum[i-]+a[i];
for i:= to n do cost[i]:=cost[i-]+a[i]*sum[i-];
for i:= to n do f[i,]:=cost[i];
for i:= to n do f[i,i-]:=;
for j:= to m do
begin
h:=; t:=; q[]:=j;
for i:=j+ to n do
begin
while (h<t) and (kx(q[h+],q[h])*sum[i]>ky(q[h+],q[h])) do inc(h);
f[i,j]:=-sum[i]*sum[q[h]]+f[q[h],j-]-cost[q[h]]+sum[q[h]]*sum[q[h]]+cost[i];
while (h<t) and (ky(i,q[t])*kx(q[t],q[t-])<=ky(q[t],q[t-])*kx(i,q[t])) do dec(t);
inc(t);
q[t]:=i;
end;
end;
writeln(f[n,m]);
end.

HDU 2829 Lawrence (斜率DP)的更多相关文章

  1. HDU 2829 - Lawrence - &lbrack;斜率DP&rsqb;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2829 T. E. Lawrence was a controversial figure during ...

  2. hdu 2829 Lawrence&lpar;斜率优化DP&rpar;

    题目链接:hdu 2829 Lawrence 题意: 在一条直线型的铁路上,每个站点有各自的权重num[i],每一段铁路(边)的权重(题目上说是战略价值什么的好像)是能经过这条边的所有站点的乘积之和. ...

  3. HDU 2829 Lawrence &lpar;斜率优化DP或四边形不等式优化DP&rpar;

    题意:给定 n 个数,要你将其分成m + 1组,要求每组数必须是连续的而且要求得到的价值最小.一组数的价值定义为该组内任意两个数乘积之和,如果某组中仅有一个数,那么该组数的价值为0. 析:DP状态方程 ...

  4. HDU 3480 - Division - &lbrack;斜率DP&rsqb;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3480 Time Limit: 10000/5000 MS (Java/Others) Memory L ...

  5. ACM-ICPC 2016 沈阳赛区现场赛 I&period; The Elder &amp&semi;&amp&semi; HDU 5956(斜率DP)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5956 题意:一颗树上每条边有个权值,每个节点都有新闻要送到根节点就是1节点,运送过程中如果不换青蛙就是 ...

  6. HDU 2829 Lawrence(斜率优化DP O(n&Hat;2))

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2829 题目大意:有一段铁路有n个站,每个站可以往其他站运送粮草,现在要炸掉m条路使得粮草补给最小,粮草 ...

  7. HDU 2829 &lbrack;Lawrence&rsqb; DP斜率优化

    解题思路 首先肯定是考虑如何快速求出一段铁路的价值. \[ \sum_{i=1}^k \sum_{j=1, j\neq i}^kA[i]A[j]=(\sum_{i=1}^kA[i])^2-\sum_{ ...

  8. HDU&period;2829&period;Lawrence&lpar;DP 斜率优化&rpar;

    题目链接 \(Description\) 给定一个\(n\)个数的序列,最多将序列分为\(m+1\)段,每段的价值是这段中所有数两两相乘的和.求最小总价值. \(Solution\) 写到这突然懒得写 ...

  9. HDU 2829 Lawrence&lpar;四边形优化DP O(n&Hat;2)&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2829 题目大意:有一段铁路有n个站,每个站可以往其他站运送粮草,现在要炸掉m条路使得粮草补给最小,粮草 ...

随机推荐

  1. &lowbar;&lowbar;weak 和 &lowbar;&lowbar;block 区别

    Blocks理解: Blocks可以访问局部变量,但是不能修改 如果修改局部变量,需要加__block __block int multiplier = 7; int (^myBlock)(int) ...

  2. MAC 安装j2ee&period;sh的办法

    It says it needs the DISPLAY variable set - what do I need to set it to? Instead of saying: ./java_e ...

  3. PHP控制前台弹出对话框

    应用场景: 微信授权登录过程中,需要用户确认,故衍生此需求: 相应的逻辑不放在前端的原因是,此部分逻辑属于偏功能业务,所以放在后端,方便统一管理. 解决办法: 通过php echo出javascrip ...

  4. c&num; 加密&sol;解密 哈希

    DES一共就有4个参数参与运作:明文.密文.密钥.向量.其中这4者的关系可以理解为: 密文=明文+密钥+向量: 明文=密文-密钥-向量: 为什么要向量这个参数呢?因为如果有一篇文章,有几个词重复,那么 ...

  5. C&num;画图解决闪烁问题

    导致画面闪烁的关键原因分析:       一.绘制窗口由于大小位置状态改变进行重绘操作时,绘图窗口内容或大小每改变一次,都要调用Paint事件进行重绘操作,该操作会使画面重新刷新一次以维持窗口正常显示 ...

  6. spring使用redis做缓存

    缓存 什么是缓存? 在高并发下,为了提高访问的性能,需要将数据库中 一些经常展现和不会频繁变更的数据,存放在存取速率更快的内存中.这样可以 降低数据的获取时间,带来更好的体验 减轻数据库的压力 缓存适 ...

  7. SQLServer导出数据到MySQL

    1从SQLServer导出数据 执行BCP: bcp "..." queryout "F:\test.txt" -c –S1.2.3.4 -Usa -P1111 ...

  8. Mysql中外键的 Cascade ,NO ACTION ,Restrict ,SET NULL

    外键约束对子表的含义: 如果在父表中找不到候选键,则不允许在子表上进行insert/update 外键约束对父表的含义: 在父表上进行update/delete以更新或删除在子表中有一条或多条对应匹配 ...

  9. 分享一个jsonp劫持造成的新浪某社区CSRF蠕虫

    最近jsonp很火,实话说已经是被玩烂了的,只是一直没有受到大家的重视.正好在上个月,我挖过一个由于jsonp造成的新浪某社区CSRF,当时是为了准备一篇文章,之后这篇文章也会拿出来分享. 因为新浪已 ...

  10. 在netcore中实现字段和属性注入

    简单来说,使用Ioc模式需要两个步骤,第一是把服务注册到容器中,第二是从容器中获取服务,我们一个一个讨论并演化.这里不会考虑使用如Autofac等第三方的容器来代替默认容器,只是提供一些简单实用的小方 ...