精华内容
下载资源
问答
  • 四边形不等式

    2018-12-28 22:12:20
    四边形不等式

    式子

    对于abcd\forall a≤b≤c≤d,满足w(a,c)+w(b,d)w(a,d)+w(b,c)w(a,c)+w(b,d)≤w(a,d)+w(b,c)

    用途

    一般是对DP的优化
    说明一点,扩,扩充在这里的意思是:
    目前有一个不等式aba≤b,已知bcb≤c,则该不等式改写为aca≤c

    证明

    定理1
    f[i,j]=min(f[i,k]+f[k+1,j]+w(i,j))f[i,j]=min(f[i,k]+f[k+1,j]+w(i,j))
    若w满足区间包含单调性和四边形不等式,
    则f也满足区间包含单调性和四边形不等式
    注意边界!
    f[i][i]=0,f[i][j]=0,(i>j)f[i][i]=0,f[i][j]=0,(i>j)
    证明
    这里的方法是,不断地凑式子,比如A<=B<=C。B是通过A凑出来的,C是通过B凑出来的。
    区间包含单调性
    abcd\forall a≤b≤c≤d,满足w(a,d)w(b,c)w(a,d)≥w(b,c)
    f的区间包含单调性?
    iikjji≤i&#x27;≤k≤j&#x27;≤j
    f[i][j]=minf[i][k]+f[k+1][j]+w(i,j)f[i][j]=min{f[i][k]+f[k+1][j]}+w(i,j)
    f[i][j]=minf[i][k]+f[k+1][j]+w(i,j)f[i&#x27;][j&#x27;]=min{f[i&#x27;][k]+f[k+1][j&#x27;]}+w(i&#x27;,j&#x27;)
    通过归纳法,可知f[i][k]f[i][k],f[k+1][j]f[k+1][j]f[i][k]≥f[i&#x27;][k],f[k+1][j]≥f[k+1][j&#x27;]
    所以,f[i][j]f[i][j]f[i][j]≥f[i&#x27;][j&#x27;]
    需要用到这个结论来进行后面的讨论。
    求证:f[a][c]+f[b][d]f[a][d]+f[b][c]f[a][c]+f[b][d]≤f[a][d]+f[b][c]
    ①当a=ba=bc=dc=d,显然成立。
    仍然使用归纳法。设当前区间[a,d][a,d]内的所有子区间满足四边形不等式。
    两种情况
    a&lt;b=c&lt;da&lt;b=c&lt;d
    a&lt;b&lt;c&lt;da&lt;b&lt;c&lt;d
    对于第一种情况,f[a][b]+f[b][d]f[a][d]+f[b][b]=f[a][d]f[a][b]+f[b][d]≤f[a][d]+f[b][b]=f[a][d]。设k=s[a][d]k=s[a][d],表示f[a][d]f[a][d]的最优决策点。
    有3种情况。
    k&lt;b,k=b,k&gt;bk&lt;b,k=b,k&gt;b
    k&lt;bk&lt;bf[a][b]+f[b][d]f[a][b]+f[b][d]≤
    f[a][k]+f[k+1][b]+w(a,b)+f[b][d]f[a][k]+f[k+1][b]+w(a,b)+f[b][d]≤ 拆项
    f[a][k]+f[k+1][d]+w(a,d)f[a][d]f[a][k]+f[k+1][d]+w(a,d)≤f[a][d] 换字母,扩
    k=bk=b,显然。
    k&gt;bk&gt;b,情况和①类似。

    a&lt;b&lt;c&lt;da&lt;b&lt;c&lt;d
    显然,函数y(k)=f[a][k]+f[k+1][b]y(k)=f[a][k]+f[k+1][b]有个最低点,当k=s[a][b]k=s[a][b]时。
    所以,将f[b][c]f[b][c]的最优决策点yyf[a][d]f[a][d]的最优决策点z找出来。
    证明方法:有待展开的2个区间,f[a][c]f[a][c]f[b][d]f[b][d]
    仍然将区间[a,d][a,d]分成区间[a,b),[b,d][a,b),[b,d]
    a&lt;byza&lt;b≤y≤z,y拆f[a][c]f[a][c],z拆f[b][d]f[b][d]
    a&lt;bzya&lt;b≤z≤y,z拆f[a][c]f[a][c],y拆f[b][d]f[b][d]
    a&lt;bzya&lt;b≤z≤y,z拆f[a][c]f[a][c],y拆f[b][d]f[b][d]
    最后都可以证明四边形不等式成立。证明方法,参考第一种情况的证明方法。

    证毕。

    用途

    定理2
    f[i][j]=minf[i][k],f[k+1][j]+w(i,j)f[i][j]=min{f[i][k],f[k+1][j]}+w(i,j)
    优化前复杂度:O(n3)O(n^3)
    优化后复杂度:O(n2)O(n^2)
    若f满足四边形不等式,则s也同时满足s[i][j1]s[i][j]s[i+1][j]s[i][j-1]≤s[i][j]≤s[i+1][j]

    先证明s[i][j1]s[i][j]s[i][j-1]≤s[i][j]。一般这种证决策单调性,用反证法。
    就是说证明s[i][j1]s[i][j]s[i][j-1]≤s[i][j]是错的。
    k1=s[i][j],k2=s[i][j1]k_1=s[i][j],k_2=s[i][j-1]
    通过不等式两边同时补某些加上这些项之后,整个式子待扩充的项,及合并,即可证明。

    s[i][j]s[i+1][j]s[i][j]≤s[i+1][j]的证明方法也是如此。

    判断

    如果abcd\forall a\leq b\leq c\leq d,满足w(a,c)+w(b,d)w(a,d)+w(b,c)w(a,c)+w(b,d)≤w(a,d)+w(b,c)
    当且仅当:w(i,j)+w(i+1,j+1)w(i,j+1)+w(i+1,j)w(i,j)+w(i+1,j+1)\leq w(i,j+1)+w(i+1,j)
    必要性显然。(有A必有B)
    证明充分性。(有B必有A)
    证明方法:整体法,换元,如将i+1i+1看成i。
    w(i,j)+w(i+1,j+1)w(i,j+1)+w(i+1,j)w(i,j)+w(i+1,j+1)≤w(i,j+1)+w(i+1,j)\Rightarrow
    w(i,j)w(i,j+1)w(i+1,j)w(i+1,j+1)w(i+2,j)w(i+2,j+1)...w(i+k,j)w(i+k,j+1)w(i,j)-w(i,j+1)≤w(i+1,j)-w(i+1,j+1)\leq w(i+2,j)-w(i+2,j+1) \leq... \leq w(i+k,j)-w(i+k,j+1)
    同理,i&lt;i+kjj+li&lt;i+k≤j≤j+l也用一样的蒸发。

    具体应用

    环形DP

    这篇博客写得好!请点这里
    给一道经典例题:

    在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。
    试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

    先不用四边形不等式优化,先将O(n3)O(n^3)的DP写出来。
    显然设dp[l][r]dp[l][r]表示[l,r][l,r]区间的答案。O(n3)O(n^3)转移显然。
    如果是不是环,直接求dp[1][n]dp[1][n]即可。

    加上环的限制?
    显然,将[1,n][1,n]复制一遍,然后求mindp[l][l+len1]min{dp[l][l+len-1]}
    这道题目是HDU3506 Monkey Party。可以在HDU上提交。

    用四边形不等式优化?
    f[i][j]=minf[i][k]+f[k+1][j]+w(i,j)f[i][j]=min{f[i][k]+f[k+1][j]+w(i,j)}
    w(i,j)=Σk=ija[k]w(i,j)=\Sigma_{k=i}^j a[k]
    显然,w(i,j)w(i,j)满足区间包含单调性和四边形不等式,所以f[i][j]f[i][j]也满足区间包含单调性和四边形不等式。
    所以,s[i][j1]s[i][j]s[i+1][j]s[i][j-1]≤s[i][j]≤s[i+1][j]
    区间DP,通常先枚举区间长度,再枚举左端点。
    伪代码

    for len=1 to n
        for l=1 to n-len+1{
            r=l+len-1;
            for k=s[l][r-1] to s[l+1][r]
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+w(l,r));
        }   
    

    时间复杂度:O(n2)O(n^2)

    证明?

    对于每个len,复杂度:Σi=1nlen+1s[i+1][i+len1]s[i][i+len2]\Sigma_{i=1}^{n-len+1} s[i+1][i+len-1]-s[i][i+len-2]
    消去很多项,最后剩下s[nlen+2][n]s[1][l1]s[n-len+2][n]-s[1][l-1],所以复杂度是O(n)O(n)的。

    赛场上

    只有那些大佬才能够推出这些东西暴虐我们。
    我们该做什么?
    打表。
    找出s[i][j]s[i][j]
    判断w(i,j)w(i,j)是否满足区间包含单调性和四边形不等式。
    f(i,j)f(i,j)是否满足区间包含单调性和四边形不等式。
    这些都可以暴力求。

    对于w(i,j)的整体感知

    这是个大难点。
    通过w(i,j)w(i,j)来设f[i][j]f[i][j]
    w(i,j)w(i,j)的意义:表示区间[i,j][i,j]的贡献。
    怎么样能够快速地求出w(i,j)w(i,j)?这个w(i,jw(i,j的复杂度不超过主DP的复杂度。一般一个式子搞定。
    比如说能够通过w(i+1,j)w(i+1,j)顺利推出w(i,j)w(i,j)w(i,j1)w(i,j-1)顺利推出w(i,j)w(i,j)

    例题

    POJ1160 Post Office
    有一个数轴n个点,第i个点的坐标为pip_i
    在n个点中选出k个作为关键点。问每个点到离其最近的关键点的距离和的最小值。
    dp[i][j]dp[i][j]表示选了i个关键点,1~j号点已经确定了哪个关键点离它们最近。
    dp[i][j]=min{dp[i][k]+w(k+1,j)}dp[i][j]=min\{dp[i][k]+w(k+1,j)\}
    这里的w(i,j)w(i,j)代表了i到j号点的花费。并且在i~j中只设立一个关键点!!!
    解决了这个问题,那么如何通过w(i+1,j)w(i+1,j)顺利推出w(i,j)w(i,j)w(i,j1)w(i,j-1)顺利推出w(i,j)w(i,j)?
    经过递推发现,
    所以,w(i,j)=w(i,j1)+p[j]p[i+j2]w(i,j)=w(i,j-1)+p[j]-p[\frac{i+j}{2}]
    w(i,j)=w(i+1,j)+p[i+j2]p[i]w(i,j)=w(i+1,j)+p[\frac{i+j}{2}]-p[i]

    然后证明ww满足四边形不等式。
    谁会去证啊?只有大佬们才去。我太弱了。

    最后说的

    四边形不等式通过决策单调性来优化复杂度的。
    那些证明的方法,受到了文化课的启发。

    展开全文
  • 四边形不等式优化

    2018-12-11 08:40:29
    四边形不等式优化

    四边形不等式优化

    在动态规划中,经常遇到形如下式的转台转移方程:
    m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(i≤k≤j)(min也可以改为max)
    上述的m(i,j)表示区间[i,j]上的某个最优值。w(i,j)表示在转移时需要额外付出的代价。该方程的时间复杂度为O(N^3)。
    下面我们通过四边形不等式来优化上述方程,首先介绍什么是”区间包含的单调性“和”四边形不等式“
    (1)区间包含的单调性:如果对于i≤i’<j≤j’,有w(i’,j)≤w(i,j’),那么说明w具有区间包含的单调性。(可以形象理解为如果小区间包含于大区间中,那么小区间的w值不超过大区间的w值)
    (2)四边形不等式:如果对于i≤i’<j≤j’,有w(i,j)+w(i’,j’)≤w(i’,j)+w(i,j’),我们称函数w满足四边形不等式。(可以形象理解为两个交错区间的w的和不超过小区间与大区间的w的和)
    下面给出两个定理
    定理一:如果上述的w函数同时满足区间包含单调性和四边形不等式性质,那么函数m也满足四边形不等式性质。
    我们再定义s(i,j)表示m(i,j)取得最优值时对应的下标(即i≤k≤j时,k处的w值最大,则s(i,j)=k)。此时有如下定理
    定理二:假如m(i,j)满足四边形不等式,那么s(i,j)单调,即s(i,j)≤s(i,j+1)≤s(i+1,j+1)。
    好了,有了上述的两个定理后,我们发现如果w函数满足区间包含单调性和四边形不等式性质,那么有s(i,j-1)≤s(i,j)≤s(i+1,j)。即原来的状态转移方程可以改写为下式:
    m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(s(i,j-1)≤k≤s(i+1,j))(min也可以改为max)
    由于这个状态转移方程枚举的是区间长度L=j-i,而s(i,j-1)和s(i+1,j)的长度为L-1,是之间已经计算过的,可以直接调用。不仅如此,区间的长度最多有n个,对于固定的长度L,不同的状态也有n个,故时间复杂度为O(N2),而原来的时间复杂度为O(N3),实现了优化!今后只需要根据方程的形式以及w函数是否满足两条性质即可考虑使用四边形不等式来优化了。

    展开全文
  • 四边形不等式证明

    2021-01-02 21:50:03
    看网上四边形不等式的证明真的是一言难尽 你家不等式的证明难道是直接蹦出来的吗 过于气愤,于是写了这篇博客 前置芝士: 四边形不等式的定义: 对于定义域为III的二元函数w(i,j)w(i,j)w(i,j),若满足∀a<b<c&...

    看网上四边形不等式的证明真的是一言难尽

    你家不等式的证明难道是直接蹦出来的吗

    过于气愤,于是写了这篇博客

    前置芝士:

    四边形不等式的定义:

    对于定义域为II的二元函数w(i,j)w(i,j),若满足a<b<c<dI,w(a,c)+w(b,d)w(a,d)+w(b,c)\forall a<b<c<d\in I,w(a,c)+w(b,d)\leq w(a,d)+w(b,c)则称函数ww满足四边形不等式

    特别的我们有另一个形式是:

    a<bI,w(a,b)+w(a+1,b+1)w(a+1,b)+w(a,b+1)\forall a<b\in I,w(a,b)+w(a+1,b+1)\leq w(a+1,b)+w(a,b+1)

    一.对于一维DP决策单调性的证明

    决策单调性的定义是:

    pip_{i}是形如fi=max0j<i(fj+val(j,i))f_{i}=max_{0\leq j <i}(f_{j}+val(j,i))的方程取到最佳决策时的jj

    我们要证的是:

    在状态转移方程fi=max0j<i(fj+val(j,i))f_{i}=max_{0\leq j <i}(f_{j}+val(j,i))中,若函数valval满足四边形不等式,则F具有决策单调性

    p[i]p[i]p[i'] \geq p[i]

    只需证:

    fi+val(p[i],i)fj+val(j,i),j[1,p[i])f_{i}+val(p[i],i') \leq f_{j}+val(j,i') , \forall j \in [1,p[i]) (1.1)(1.1)

    我们得到上述不等式即可

    考虑构造四边形不等式:

    cost(j,i)+cost(p[i],i)cost(j,i)+cost(p[i],i)cost(j,i')+cost(p[i],i) \geq cost(j,i)+cost(p[i],i')

    移项:

    cost(j,i)cost(j,i)cost(p[i],i)cost(p[i],i)cost(j,i')-cost(j,i) \geq cost(p[i],i')-cost(p[i],i) (1.2)(1.2)

    由题设出发有:

    fi+cost(p[i],i)fi+cost(j,i),j[1,p[i])f_{i}+cost(p[i],i) \leq f_{i}+cost(j,i),\forall j \in [1,p[i]) (1.3)(1.3)

    (1.2)+(1.3)(1.2)+(1.3)即得:

    fi+val(p[i],i)fj+val(j,i),j[1,p[i])f_{i}+val(p[i],i') \leq f_{j}+val(j,i') , \forall j \in [1,p[i])

    (1.1)(1.1)

    证毕.

    展开全文
  • 四边形不等式应用

    2020-01-10 13:18:44
    动态规划加速原理之四边形不等式 动态规划的四边形不等式优化是对特定形式的状态转移方程进行优化的一种方法,该方法可以将复杂度由 O(n3)O(n^3)O(n3) 优化到 O(n2)O(n^2)O(n2)。 设我们有状态转移方程 m(i,j)={min{...

    动态规划加速原理之四边形不等式

    动态规划的四边形不等式优化是对特定形式的状态转移方程进行优化的一种方法,该方法可以将复杂度由 O(n3)O(n^3) 优化到 O(n2)O(n^2)

    设我们有状态转移方程

    m(i,j)={min{m(i,k1)+m(k,j)+w(i,j)}i<j0i=jINFi>j m(i ,j) =\left\{ \begin{array}{rcl} min \{ m(i , k - 1) + m(k , j) + w(i , j) \} & & {i< j}\\ 0 & & i = j\\ INF & & i > j \end{array} \right.

    w 满足区间包含的单调性:
    如果对于 i <= i’ < j <= j’ 都有 w(i’ , j ) <= w(i ,j’) ,那么称函数 w 满足关于区间包含的单调性。

    w 满足四边形不等式:
    如果对于 i <= i’ < j <= j’ 都有 w(i , j ) + w(i’ , j’) <= w(i ’ , j ) + w( i , j’ ),我们称 w 满足四边形不等式。

    m 满足四边形不等式:
    如果 w 满足区间包含的单调性,同时又满足四边形不等式,那么 m 函数也满足四边形不等式。

    m 满足四边形不等式的应用:
    定义 s( i , j ) 为函数 m(i , j) 对应的决策变量的最大值。如果 m(i ,j) 满足四边形不等式,那么 s(i , j) 单调。
    原状态转移方程可表示为:
    m(i,j)=m(i,k1)+m(k,j)+w(i,j)m(i ,j) = { m(i , k - 1) + m(k , j) + w(i , j) }
    其中 s(i,j1)<=k<=s(i+1,j)s(i, j - 1) <= k <= s(i+1 , j) 。如此变将第三层枚举数量减少,时间复杂度优化到了 O(n2)O(n^2)

    例题

    例1:石子合并

    题意描述
    共 n 堆石子围成一圈,每次可以选定相邻两堆合并成一堆,得分为合并后的新堆的石子数量,请问将这 n 堆石子合并成一堆的最小值是多少?

    例2:HDU3480 Division

    题意简述
    给定 n 个元素,请将这 n 个元素分为 m 个集合,每个集合的得分为该集合内的(最大值-最小值)^2。请问最少得分是多少。

    解题思路
    因为我们可以任选元素放入子集,所以元素的顺序没有规定。我们将元素按照大小排序,这样选中连续的 k 个一定是所有大小为 k 的子集中得分最少的。可以通过反证法来证明,将这 k 个元素中的任一个替换都会使得得分增加。
    可以用动态规划来解决,设 f[i ,j] 表示将前 j 个元素分为 j 个集合最少得分。那么 f[ i , j ] = min{ f[k , j-1] + w(k+1 , i) },其中 w 为计算集合得分的函数,1 <= k < i。

    这样做的时间复杂度为 O(N^3),由于本题数据过大,因此会超时,可以考虑是否能用四边形不等式优化。

    判断是否能用四边形不等式优化
    假设 a <= b < c <= d;由于序列是顺序排序,所以元素大小和下标成正比,因此用下标代替元素。

    考虑 w( b , c) < w(a , d)是否成立:显然由于元素是递增的,所以 (da)2>(cb)2(d - a)^2 > (c - b)^2,即满足区间包含的单调性。
    考虑w(a , c) + w(b , d) <= w(a , d) + w(b , c)是否成立:
    (ca)2+(db)2<=(da)2+(cb)2(c-a)^2 + (d-b)^2 <= (d-a)^2 + (c-b)^2 是否成立;
    化简后即 ac+bd>ad+bcac + bd > ad + bc 是否成立;
    即 b(d-c) >= a(d-c) 是否成立;
    由于 d > c,b > a,所以 上式成立,原式得证。

    综上所述 w 函数既满足区间包含单调性又满足四边形不等式,所以可以用四边形不等式优化。

    利用 s 数组进行四边形不等式优化

    我们知道四边形不等式的优化主要在于减少了中间状态的枚举,我们设 s[i , j] 为 f[i ,j] 取最小值时的中间变量 k。
    那么我们状态转移方程就可以变成 f[ i , j ] = min{ f[k , j-1] + w(k+1 , i) },其中 s[i ,j-1] <= k < s[i+1 ,j] 。
    初始化而言,f[i ,1] = w(i ,1),即把前 i 个元素分为一个子集;s[i , 1] = 1,即前 i 个元素分为一个子集时起点为 1 。
    因为集合的划分个数要从小到大,所以集合个数 j 就从 2 开始,放在最外层;第二层因为要用到 s[i+1 ,j] ,所以 i 要从后向前遍历更新;中间就是利用 s 数组进行四边形不等式优化了。

    在用 s 数组替换原始范围时,一定要注意范围,尤其是边界范围是否一致,同时要注意 s 数组的加入是否会影响更新顺序。

    代码示例

    #include<cstdio>
    #include<algorithm>
    const int N = 1e4+10;
    const int M = 5010;
    typedef int ll;
    ll a[N],f[N][M];
    const ll INF = 0x3f3f3f3f;
    int t,n,m,s[N][M];
    ll getInt(){
    	char c = getchar();
    	bool neg = false;
    	ll res = 0;
    	while(c != '-' && (c < '0' || c > '9')) c = getchar();
    	if(c == '-') neg = true,c = getchar();
    	while(c >= '0' && c <= '9') res = res*10+c-'0',c = getchar();
    	return neg?-res:res;
    }
    inline ll w(int l,int r){
    	return (a[r]-a[l])*(a[r]-a[l]);
    }
    ll solve(){
    	/* 计算并返回答案 */
    	n = getInt(); m = getInt();
    	for(int i = 1;i <= n;i++) a[i] = getInt();
    	std::sort(a+1,a+1+n);
    	for(int i = 1;i <= n;i++) f[i][1] = w(1,i), s[i][1] = 1,s[n+1][i] = n-1;
    	for(int j = 2;j <= m;j++)
    		for(int i = n;i >= j;i--){
    			f[i][j] = INF;
    			for(int k = s[i][j-1];k <= s[i+1][j];k++)
    				if(f[i][j] >= f[k][j-1] + w(k+1,i)){
    					f[i][j] = f[k][j-1] + w(k+1,i);
    					s[i][j] = k;
    				}
    		}
    			
    	return f[n][m];
    }
    int main(){
    	scanf("%d",&t);
    	for(int c = 1;c <= t;c++)
    		printf("Case %d: %d\n",c,solve());
    	return 0;
    }
    

    参考资料

    • 动态规划加速原理之四边形不等式,赵爽
    展开全文
  • 四边形不等式与决策单调 四边形不等式 一维线性DP的优化 二维区间递推优化 四边形不等式与决策单调 四边形不等式 定义 存在二元函数\(w(x,y)\) ,其定义域为\(I\), 若对于任意\(a,b,c,d\in I且a≤b≤c≤...
  • 四边形不等式简析

    2018-08-07 22:05:00
    并不是很透彻,只是切掉了一道模板题。 [TOC] 四边形不等式 不等式 w(i,j)w(i,j),对于∀a≤b≤c≤d∀a≤b≤c...
  • 四边形不等式的运用

    2019-10-30 21:02:34
    四边形不等式的运用 四边形不等式的定义: 对于定义域上的任意整数a,b,c,d,其中a≤b≤c≤da\le b \le c \le da≤b≤c≤d 都有w(a,d)+w(b,c)≥w(a,c)+w(b,d)w(a,d)+w(b,c)\ge w(a,c)+w(b,d)w(a,d)+w(b,c)≥w(a,c)+w(b...
  • 四边形不等式优化讲解(详解)

    万次阅读 多人点赞 2017-05-19 08:15:40
    累加器传送门: ... 什么是四边形不等式 S. 四边形不等式优化如何证明 T. 怎么用四边形不等式优化 (感谢博客园的Staginner,他的博客对我有很大影响) 这是他的博客: http://www.cnblogs.com/staginn
  • 四边形不等式优化dp专题

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 756
精华内容 302
关键字:

四边形不等式