dp优化-四边形不等式(模板题:合并石子)
学习博客:https://blog.csdn.net/noiau/article/details/72514812
看了好久,这里整理一下证明
方程形式:dp(i,j)=min(dp(i,k)+dp(k+1,j))+cost(i,j) O(n^3)
四边形不等式:将其优化为O(n^2)
1.四边形不等式
a<b<=c<d
f(a,c)+f(b,d)<=f(b,c)+f(a,d)交叉小于包含
则对于i<i+1<=j<j+1
f(i,j)+f(i+1,j+1)<=f(i+1,j)+f(i,j+1)
f(i,j)-f(i+1,j)<=f(i,j+1)-f(i+1,j+1)
令g(j)=f(i,j)-f(i+1,j),则g(j)递增
2.若cost(i,j)有凸性,则dp(i,j)也有凸性
只需要证明对任意i<i+1<=j<j+1,有dp(i,j)+dp(i+1,j)<=dp(i+1,j)+dp(i,j+1)
设dp(i+1,j)取最优解的k=x,dp(i,j+1)取最优解的k=y
即要证:dp(i,j)+dp(i+1,j)<=dp(i,y)+dp(y+1,j+1)+dp(i+1,x)+dp(x+1,j)+cost(i,j+1)+cost(i+1,j)(1)
令A=dp(i,y)+dp(y+1,j+1)+dp(i+1,x)+dp(x+1,j);
由于dp(i,j)的最优解不一定为k=x,则dp(i,j)<=dp(i,x)+dp(x+1,y)+cost(i,j)
同理由于dp(i+1,j)的最优解不一定为k=y,则dp(i+1,j)<=dp(i+1,y)+dp(y+1,j)+cost(i+1,j)
(1)式可化为:
dp(i,j)+dp(i+1,j)<=A+cost(i,j)+cost(i+1,j)<=A+cost(i,j+1)+cost(i+1,j)
由cost的凸性可知成立,故dp(i,j)也有凸性
3.证明决策的单调性
设s(i,j)表示dp(i,j)最优时的k值
要证:s(i,j-1)<=s(i,j)<=s(i+1,j)
先证s(i,j-1)<=s(i,j):
设y=s(i,j-1),对任意x满足x<=y<j-1<j,有x+1<=y+1<=j-1<j
由四边形不等式:dp(x+1,j-1)+dp(y+1,j)<=dp(x+1,j)+dp(y+1,j-1)
令A=dp(i,x)+cost(i,j-1)+dp(i,y)+cost(i,j)
两边同时加上A
化简得到:dp(i,j-1)(k=x时的值)+dp(i,j)(k=y)<=dp(i,j)(k=x)+dp(i,j-1)(k=y)
移项:dp(i,j-1)(k=x)-dp(i,j-1)(k=y)<=dp(i,j)(k=x)-dp(i,j)(k=y)
由于k=y时dp(i,j-1)取最小值,则左边>=0,即dp(i,j)(k=x)>=dp(i,j)(k=y)
也就是说,对于dp(i,j),任意一个k=x<y都不如k=y优。
故s(i,j-1)<=s(i,j)
另一边同理(不证了)
那么关键就在于枚举k的部分
//s(i,j-1)<=s(i,j)<=s(i+1,j)
for(int i=n;i>=;i--)
(int j=i+;j<=n;j++)
{
int d=INF,id=;
for(int k=s[i][j-];k<=s[i+][j];k++)
{
if(d>dp[i][k]+dp[k+][j]+sum[j]-sum[i-])
{
d=dp[i][k]+dp[k][j]+sum[j]-sum[i-];
id=k;
}
}
dp[i][j]=d;
s[i][j]=id;
}
总复杂度O(n^2)
补充一个证明
来源为https://www.cnblogs.com/mlystdcall/p/6525962.html,我稍微加了一点点
对于固定的区间长度len,有
dp[i][i+len]的决策范围为s[i][i+len-1]至s[i+1][i+len]
dp[i+1][i+len+1]的决策范围为s[i+1][i+len]至s[i+2][i+len+1]
dp[i+2][i+len+2]的决策范围为s[i+2][i+len+1]至s[i+3][i+len+2]
如此脑补下去,我们发现,对于固定的区间长度len,总共的决策只有O(n)个!因为一共有O(n)个不同的区间长度len,所以算法的总复杂度就是O(n^2)!
模板题:合并石子
现在有n堆石子,要将石子按一定顺序地合成一堆,规定如下,每次只能移动相邻的两堆石子,合并费用为新和成一堆石子的数量,求把n堆石子全部合并到一起所花的最少或者最大花费
很容易想到这样一个dp转移
dp[i][j]=min{dp[i][k]+dp[k+1][j]}+cost[i][j]
震惊!这不就是之前所讲的模型嘛?原来之前O(n^3)方的合并石子问题还可以优化(我太弱了)
首先明确一点,cost[i][j]表示把第i堆到第j堆的石子和到一起的最后一步的代价,显然,之前无论怎么合并,最后一步的代价都是一样的,所以我们可以先预处理出这个cost数组,他等于cnt[j]-cnt[i-1],其中cnt数组是前缀和
---------------------
作者:NOIAu
来源:CSDN
原文:https://blog.csdn.net/noiau/article/details/72514812
版权声明:本文为博主原创文章,转载请附上博文链接!
分析题目:
只要证明cost(i,j)满足凸性。g(j)=cost(i,j)-cost(i+1,j)=sum(j)-sum(i-1)-sum(j)+sum(i)=sum(i)-sum(i-1)与j无关,满足(此时为等于)。
我的模板:
#include<bits/stdc++.h>
using namespace std; const int N=,INF=(int)1e9;
int dp[N][N],s[N][N],sum[N]; int main()
{
//freopen("a.in","r",stdin);
int n;
scanf("%d",&n);
sum[]=;
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
sum[i]=sum[i-]+x;
}
for(int i=;i<=n;i++) dp[i][i]=,s[i][i]=i;
//s(i,j-1)<=s(i,j)<=s(i+1,j)
for(int i=n;i>=;i--)
(int j=i+;j<=n;j++)
{
int d=INF,id=;
for(int k=s[i][j-];k<=s[i+][j];k++)
{
if(d>dp[i][k]+dp[k+][j]+sum[j]-sum[i-])
{
d=dp[i][k]+dp[k][j]+sum[j]-sum[i-];
id=k;
}
}
dp[i][j]=d;
s[i][j]=id;
}
printf("%d\n",dp[][n]);
return ;
}
最新文章
- Docker:镜像操作和容器操作
- [转]nginx+fastcgi+c/c++搭建高性能Web框架
- 定义label标签宽度需要设置display:inline-block;
- VS2010编译、调用Lua程序
- [Locked] Zigzag Iterator
- java中保留几位小数
- VS快捷方式小技巧
- python 字符串探讨
- 转:什么是FOUC?如何避免FOUC?
- SolrCloud简介
- MySQL 改动用户password及重置rootpassword
- 201521123029《Java程序设计》第14周学习总结
- teeporxy.go
- Python调用ansible API系列(四)动态生成hosts文件
- IDEA添加项目依赖(将Tomcat中的servlet-api.jar添加到项目中去)
- vuforia unity 识别图片出模型
- 【做题】SDOI2017硬币游戏——方程&概念处理
- spring boot -thymeleaf-url
- 远程桌面连接MySQL遇到的问题及解决方法总结
- 前端安全 -- XSS攻击
热门文章
- Notes of the scrum meeting before publishing(12.19)
- 寒假作业end
- UVALive - 6869 Repeated Substrings 后缀数组
- RabbitMQ安装与初始配置【转载】
- WPF 资源应用
- set(gcf,&#39;DoubleBuffer&#39;,&#39;on&#39;)
- bzoj3676-回文串
- BZOJ 1045 糖果传递(思维)
- 使用for循环遍历数组元素
- 【题解】NOIP2015推销员