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

    2021-10-22 11:10:36
    四边形不等式优化 四边形不等式 1、若对于∀a,b,c,d∈Za≤b≤c≤d有Wa,d+Wb,c≥Wa,c+Wb,d 1、若对于 \forall a,b,c,d \in Z \quad a \le b \le c \le d 有 \quad W_{a,d} + W_{b,c} \ge W_{a,c} + W_{b,d} 1、若对于...

    四边形不等式优化

    四边形不等式

    1 、 若 对 于 ∀ a , b , c , d ∈ Z a ≤ b ≤ c ≤ d 有 W a , d + W b , c ≥ W a , c + W b , d 1、若对于 \forall a,b,c,d \in Z \quad a \le b \le c \le d 有 \quad W_{a,d} + W_{b,c} \ge W_{a,c} + W_{b,d} 1a,b,c,dZabcdWa,d+Wb,cWa,c+Wb,d

    2 、 若 对 于 ∀ a , b ∈ Z a < a + 1 ≤ b < b + 1 有 W a , b + W a + 1 , b + 1 ≥ W a , b + 1 + W a + 1 , b 2、若对于 \forall a,b \in Z \quad a \lt a+1 \le b \lt b+1 有 \quad W_{a,b} + W_{a+1,b+1} \ge W_{a,b+1} + W_{a+1,b} 2a,bZa<a+1b<b+1Wa,b+Wa+1,b+1Wa,b+1+Wa+1,b

    • 其中12结论等价

    一维DP的四边形不等式优化

    对于形如
    f i = m i n 0 ≤ j < i { f j + V i , j } f_i = min_{0 \le j \lt i} \{ f_j + V_{i,j}\} fi=min0j<i{fj+Vi,j}
    形式的状态转移方程,如果Vi,j满足四边形不等式,则决策具有单调性,即
    0 ≤ j ≤ p < i ≤ i ′ p 为 决 策 , j 为 决 策 前 的 任 意 点 0 \le j \le p \lt i \le i' \qquad p为决策,j为决策前的任意点 0jp<iipj

    f p + V p , i ≤ f j + V j , i f_p + V_{p,i} \le f_j + V_{j,i} fp+Vp,ifj+Vj,i

    • 因为具有决策单调性,因此我们使用类似于单调队列的方式对决策点进行存储:

    使用三元组(j,l,r)表示在[l,r]区间上的最优决策为j,每次状态转移完之后

    1、如果队头的右端点刚好越过,则弹出队头,更新队头的左端点

    2、将此决策点插入队尾 :如果队尾的决策点的左端点决策不如当前点优,即全部弹出队尾,如果左端点优于当前点但是右端点不优于新插点,二分得到二段性点,修改队尾的区间并将新点插入队尾

    二维四边形不等式

    对于形如
    f i , j = m i n i ≤ k ≤ j { f i , k + f k + 1 , j + W i , j } f_{i,j} = min_{i \le k\le j}\{f_{i,k} + f_{k+1,j} + W_{i,j}\} fi,j=minikj{fi,k+fk+1,j+Wi,j}
    (1)若满足边界f(i,i) = W(i,j) = 0

    (2)若W(i,j)满足四边形不等式

    (3)对于任意 a <= b <= c <= dW(a,d) >= W(b,c)

    若满足上述三个条件,则f(i,j)也满足四边形不等式

    P(i,j)为决策点,则决策具有二维单调性,因此在状态转移的时候,x只需要枚举从p(i-1,j)p(i,j+1)即可,时间复杂度由O(n^3) 优化至O(n^2)

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

    2019-09-23 10:56:35
    声明: 本文转载自网易博客: ...四边形不等式优化_石子合并问题_C++  在动态规划中,经常遇到形如下式的状态转移方程:  m(i,j)=min{m(i,k-1),m(k,j)}+w(i,j)(i≤k≤j)(min也可以改为max...

    声明:

    本文转载自网易博客:

        http://blog.163.com/dqx_wl/blog/static/2396821452015111133052112/

    四边形不等式优化_石子合并问题_C++

      在动态规划中,经常遇到形如下式的状态转移方程:

        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(N3)

       

      下面我们通过四边形不等式来优化上述方程,首先介绍什么是“区间包含的单调性”和“四边形不等式”

        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的和)

     

      下面给出两个定理:

        1、如果上述的 w 函数同时满足区间包含单调性和四边形不等式性质,那么函数 m 也满足四边形不等式性质

           我们再定义 s(i,j) 表示 m(i,j) 取得最优值时对应的下标(即 i≤k≤j 时,k 处的 w 值最大,则 s(i,j)=k)。此时有如下定理

        2、假如 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(N^2),而原来的时间复杂度为 O(N^3),实现了优化!

      今后只需要根据方程的形式以及 w 函数是否满足两条性质即可考虑使用四边形不等式来优化了。

     

      以上描述状态用 m(i,j),后文用的 dp[i][j],所代表含意是相同的,特此说明。

      以石子合并问题为例。

      例如有6堆石子,每堆石子数依次为3 4 6 5 4 2

      因为是相邻石子合并,所以不能用贪心(每次取最小的两堆合并),只能用动归。(注意:环形石子的话,必须要考虑最后一堆和第一堆的合并。)

      例如:一个合并石子的方案:

        第一次合并 3 4 6 5 4 2 ->7

        第二次合并 7 6 5 4 2 ->13

        第三次合并 13 5 4 2 ->6

        第四次合并 13 5 6 ->11

        第五次合并 13 11 ->24

      总得分=7+6+11+13+24=61 显然,比贪心法得出的合并方案(得分:62)更优。

      

      动归分析类似矩阵连乘等问题,得出递推方程:

        设 dp[i][j] 表示第 i 到第 j 堆石子合并的最优值,sum[i][j] 表示第 i 到第 j 堆石子的总数量。

        (可以在计算开始先做一遍求所有的 sum[i],表示求出所有第1堆到第i堆的总数量。则 sum[i][j]=sum[j]-sum[i]。这样计算比较快。)

      那么就有状态转移公式:

          

        这里 i<=k<j

      普通解法需要 O(n^3)。下面使用四边形不等式进行优化。

      首先判断是否符合区间单调性和四边形不等式。

         i  i'    j    j'

        3 4 6 5 4 2

      单调性:

        w[i',j] = 4+6+5=15 w[i,j'] =3+4+6+5+4+2=24

      故w[i',j] <= w[i,j'] 满足单调性

      四边形不等式:

        w[i,j] + w[i',j'] = (3+4+6+5) + (4+6+5+4+2) = 18+21 = 39

        w[i',j] + w[i,j'] = (4+6+5) + (3+4+6+5+4+2) = 15 + 24 = 39

        故 w[i,j] + w[i',j'] <= w[i',j] + w[i,j']

      故石子合并可利用四边形不等式进行优化。

     

      利用四边形不等式,将原递推方程的状态转移数量进行压缩(即缩小了k的取值范围)。

      令 s[i][j]=min{k | dp[i][j] = dp[i][k-1] + dp[k][j] + w[i][j]},即计算出 dp[i][j] 时的最优的 k 值(本例中寻优为取最小)

      也可以称为最优决策时的 k 值。由于决策 s 具有单调性,因此状态转移方程中的 k 的取值范围可修改为 :

        s[i,j-1] <= s[i,j] <= s[i+1,j]

        边界:s[i,i] = i

      因为 s[i,j] 的值在 m[i,j] 取得最优值时,保存和更新,因此 s[i,j-1] 和 s[i+1,j] 都在计算 dp[i][j-1] 以及 dp[i+1][j] 的时候已经计算出来了。

      因此,s[i][j] 即 k 的取值范围很容易确定。

      根据改进后的状态方程,以及 s[i][j] 的定义方程,可以很快的计算出所有状态的值。计算过程可以如下表所示(类似于矩阵连乘的打表)。

      状态表(如果是环形石子合并,需要打2n*2n的表)

        3 4 6 5 4 2

      

      例如:

        计算dp[1][3],由于s[1][2]=1,s[2][3]=2,则k值的取值范围是1<=k<=2

        则,dp[1][3]=min{dp(1,1)+dp(2,3)+13, dp(1,2)+dp(3,3)+13}=min{10+13, 7+13}=20,将其填到状态表。同时,由于取最优值的k等于2,则将其填到s表。

        同理,可以计算其他状态表和s表中的值。

          dp[2][4]=min{dp(2,2)+dp(3,4)+15, dp(2,3)+dp(4,4)+15}=min{11+15, 10+15}=25

          k=3

        从表中可以看出,当计算dp[2][5]的时候,由于s[ i,j-1]=s[ 2,4]=3,s[ i+1,j]=s[3,5]=3,此时k的取值范围已经限定为只有一个,大幅缩短了寻找最优解的时间。

     

      这里给出程序代码:

    复制代码
     1 #include<iostream>
     2 #include<cstdio>
     3 using namespace std;  4  5 const int N=205;  6 const int INF=0x7fffffff;  7 int n;  8 int a[N],sum[N],dp[N][N],s[N][N];  9 void f(); 10 int main() 11 { 12 while(~scanf("%d",&n)) 13  { 14 sum[0]=0; 15 for (int i=1;i<=n;i++) 16  { 17 scanf("%d",&a[i]); 18 sum[i]=sum[i-1]+a[i]; 19  } 20  f(); 21 printf("%d\n",dp[1][n]); 22  } 23 return 0; 24 25 } 26 void f() 27 { 28 for (int i=1;i<=n;i++) dp[i][i]=0,s[i][i]=i; 29 for (int r=1;r<n;r++) 30  { 31 for (int i=1;i<n;i++) 32  { 33 int j=i+r; 34 if(j>n) break; 35 dp[i][j]=INF; 36 for (int k=s[i][j-1];k<=s[i+1][j];k++) 37  { 38 if(dp[i][j]>dp[i][k]+dp[k+1][j]) 39  { 40 dp[i][j]=dp[i][k]+dp[k+1][j]; 41 s[i][j]=k; 42  } 43  } 44 dp[i][j]+=sum[j]-sum[i-1]; 45  } 46  } 47 }
    复制代码

     

     

     

    转载于:https://www.cnblogs.com/zzqc/p/7296484.html

    展开全文
  • } } } } 注意: ① maxmaxmax不符合四边形不等式,且可以证明最大值 f(i,j)f(i,j)f(i,j)的最优决策点一定在区间两端取到. 例题二:[HDU2829] Lawrence 令 dp(i,j)dp(i,j)dp(i,j)代表前 iii个数,分成 jjj段的最小值....

    0.前言:

    大概大一下学期还是啥时候就听说过这个优化了。现在都大三下了才正式开始学这东西,哈哈,太垮了.这里只记录结论和如何使用。不说证明(也看不懂.

    1.使用场合:

    优化转移:
    1. d p ( i , j ) = m i n { d p ( i , k ) + d p ( k , j ) + w ( i , j ) } dp(i,j)=min\{dp(i,k)+dp(k,j)+w(i,j)\} dp(i,j)=min{dp(i,k)+dp(k,j)+w(i,j)}
    2. d p ( i , j ) = m i n { d p ( i − 1 , k − 1 ) + w ( k , j ) } dp(i,j)=min\{dp(i-1,k-1)+w(k,j)\} dp(i,j)=min{dp(i1,k1)+w(k,j)}

    解释: d p ( i , j ) dp(i,j) dp(i,j)是区间形式且他们存在着一个最优决策点 k k k使得 d p ( i , j ) dp(i,j) dp(i,j)取最小值.

    第一种转移:石子合并模型
    第二种转移:将长度为 n n n的序列分成 m m m段,求最小值.

    2.使用条件:

    w ( i , j ) w(i,j) w(i,j)满足 四边形不等式以及单调性 能够推出 d p ( i , j ) dp(i,j) dp(i,j)也满足.

    在这里插入图片描述

    2.1:四边形不等式:两个交错区间的 w w w和,小于等于 小区间与大区间的 w w w和。

    2.2:单调性:小区间的 w w w 小于等于 大区间的 w w w.

    只要满足这两个条件即可使用。

    3.min与max

    如果把min改成max,那么使用条件就正好得反过来:

    w ( i , j ′ ) + w ( i ′ , j ) ≥ w ( i , j ) + w ( i ′ , j ′ ) w(i,j')+w(i',j) \geq w(i,j)+w(i',j') w(i,j)+w(i,j)w(i,j)+w(i,j) - 反四边形不等式

    w ( i ′ , j ) ≥ w ( i , j ′ ) w(i',j) \geq w(i,j') w(i,j)w(i,j) - 单调性:小区间的值大于等于大区间的值

    4.优化方法:

    s ( i , j ) s(i,j) s(i,j)记录区间最优决策点,如果 d p ( i , j ) dp(i,j) dp(i,j)满足四边形不等式,则:
    s ( i , j − 1 ) ≤ s ( i , j ) ≤ s ( i + 1 , j ) s(i,j - 1) \leq s(i,j) \leq s(i+1,j) s(i,j1)s(i,j)s(i+1,j)

    复杂度降至: O ( n 2 ) O(n^2) O(n2)

    5.结论:

    其实四边形不等式优化就是二维的决策单调性优化.

    一维决策单调性也可以使用四边形不等式优化!

    6.例题:

    例题一:石子合并(模板)
    for (int len = 2 ; len <= m ; len++){
        for (int i = 1 ; i + len - 1 <= m ; i++){
            int j = i + len - 1;
            int cost = p[j] - p[i - 1];
            for (int k = s[i][j - 1] ; k <= s[i + 1][j] ; k++){
                if (dp[i][j] > dp[i][k] + dp[k + 1][j] + cost){
                    dp[i][j] = dp[i][k] + dp[k + 1][j] + cost;
                    s[i][j] = k;
                }
            }
        }
    }
    

    注意:
    m a x max max不符合四边形不等式,且可以证明最大值 f ( i , j ) f(i,j) f(i,j)的最优决策点一定在区间两端取到.

    例题二:[HDU2829] Lawrence

    d p ( i , j ) dp(i,j) dp(i,j)代表前 i i i个数,分成 j j j段的最小值.有转移:
    d p ( i , j ) = m i n { d p ( k − 1 , j − 1 ) + w ( k , j ) } , k ∈ [ 1 , i ] dp(i,j)=min\{dp(k-1,j-1)+w(k,j)\},k\in[1,i] dp(i,j)=min{dp(k1,j1)+w(k,j)},k[1,i]

    属于形式 2 2 2.复杂度: O ( n 2 m ) O(n^2m) O(n2m)。展开计算发现其符合四边形不等式以及单调性.优化 k k k的枚举即可.

    这里注意最优决策点的范围在 [ s [ i ] [ j − 1 ] , s [ i + 1 ] [ j ] ] [s[i][j-1],s[i+1][j]] [s[i][j1],s[i+1][j]].所以得考虑一个正确的dp顺序和初始化s数组边界:

    1.外层顺序枚举 j , 2 = > m j,2=>m j,2=>m,内层逆序枚举 i , n = > 1 i,n=>1 i,n=>1.
    2. s [ i ] [ 1 ] = 1 , s [ n + 1 ] [ i ] = n s[i][1]=1,s[n+1][i]=n s[i][1]=1,s[n+1][i]=n

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define pii pair<int,int>
    #define pb push_back
    #define mp make_pair
    #define vi vector<int>
    #define vl vector<ll>
    const int maxn = 1005 + 5;
    const int mod = 1e9 + 7;
    ll a[maxn] , dp[maxn][maxn] , p[maxn] , pp[maxn];
    int s[maxn][maxn];
    ll calc (int l , int r)
    {
        ll g = p[r] - p[l - 1];
        g *= g;
        g -= pp[r] - pp[l - 1];
        g /= 2;
        return g;
    }
    int main()
    {
        ios::sync_with_stdio(false);
        int n , m;
        while (cin >> n >> m , n && m){
            m++;
            for (int i = 1 ; i <= n ; i++){
                cin >> a[i];
                p[i] = p[i - 1] + a[i];
                pp[i] = pp[i - 1] + a[i] * a[i];
            }
            for (int i = 0 ; i <= n ; i++)
                for (int j = 0 ; j <= m ; j++)
                    dp[i][j] = 1e15;
            dp[0][0] = 0;
            // 边界
            for (int i = 1 ; i <= n ; i++){
                dp[i][1] = calc(1 , i);
                s[i][1] = 1;
            }
            // s[i][j-1] <= s[i][j] <= s[i+1][j]
            // 考虑如何安排dp顺序
            for (int j = 2 ; j <= m ; j++){
                s[n + 1][j] = n;
                for (int i = n ; i >= 1 ; i--){
                    for (int k = s[i][j - 1] ; k <= s[i + 1][j] ; k++){
                        if (dp[k - 1][j - 1] + calc(k , i) < dp[i][j]){
                            dp[i][j] = dp[k - 1][j - 1] + calc(k , i);
                            s[i][j] = k;
                        }
                    }
                }
            }
            cout << dp[n][m] << endl;
        }
        return 0;
    }
    
    展开全文
  • Part.0 前置知识 简单的 DP 方法; 数学推理能力。...一般来讲,四边形不等式可以用来优化形如下面的转移方式的 DP: f(l,r)=min⁡k=lr−1{f(l,k)+f(k+1,r)}+w(l,r) f(l, r) = \min\limits_{k = l...

    Part.0 前置知识

    • 简单的 DP 方法;
    • 简单的 数学推理能力。

    Part.1 四边形不等式

    高能数学公式警告

    Part.1/1 四边形不等式的概念

    四边形不等式优化主要应用于区间 DP 的优化。一般来讲,四边形不等式可以用来优化形如下面的转移方式的 DP:

    f ( l , r ) = min ⁡ k = l r − 1 { f ( l , k ) + f ( k + 1 , r ) } + w ( l , r ) f(l, r) = \min\limits_{k = l}^{r - 1}\{f(l, k) + f(k + 1, r)\} + w(l, r) f(l,r)=k=lminr1{f(l,k)+f(k+1,r)}+w(l,r)

    其中, w ( l , r ) w(l, r) w(l,r) 表示选择区间 [ l , r ] [l, r] [l,r] 的代价。

    这样如果直接转移的话复杂度会达到 O ( N 3 ) O(N^3) O(N3) ,然而当 w ( l , r ) w(l, r) w(l,r) 满足如下性质后,复杂度就会优化到 O ( N 2 ) O(N^2) O(N2)

    • 区间包含单调性: 对于任意的 l ≤ l ′ ≤ r ′ ≤ r l \le l' \le r' \le r llrr,均有 w ( l ′ , r ′ ) ≤ w ( l , r ) w(l', r') \le w(l, r) w(l,r)w(l,r) 成立,则称 w w w 有区间包含单调性。
    • 四边形不等式: 对于任意的 l 1 ≤ l 2 ≤ r 1 ≤ r 2 l_1 \le l_2 \le r_1 \le r_2 l1l2r1r2,均有 w ( l 1 , r 1 ) + w ( l 2 , r 2 ) ≤ w ( l 1 , r 2 ) + w ( l 2 , r 1 ) w(l_1, r_1) + w(l_2, r_2) \le w(l_1, r_2) + w(l_2, r_1) w(l1,r1)+w(l2,r2)w(l1,r2)+w(l2,r1) 成立,则称函数 w w w 满足四边形不等式。特别地,当等号永远成立时,我们称函数 w w w 满足四边形恒等式。

    Part.1/2 证明 f ( l , r ) f(l, r) f(l,r) 满足四边形不等式

    引理: w w w 同时满足区间包含单调性和四边形不等式,那么 f f f 也满足四边形不等式。


    证明: 采用数学归纳法进行证明。我们对区间长度进行归纳。

    l 1 ≤ l 2 ≤ r 1 ≤ r 2 l_1 \le l_2 \le r_1 \le r_2 l1l2r1r2,记 u u u f ( l 1 , r 2 ) f(l_1, r_2) f(l1,r2) 的最优决策点, v v v f ( l 2 , r 1 ) f(l_2, r_1) f(l2,r1) 的最优决策点。

    则分成两种情况讨论:

    情况(1): u ≤ v u \le v uv。显然有 l 1 ≤ u < r 1 , l 2 ≤ v < r 2 l_1\le u < r_1, l_2 \le v < r_2 l1u<r1,l2v<r2

    得到不等式组:

    { f ( l 1 , r 1 ) ≤ f ( l 1 , u ) + f ( u + 1 , r 1 ) + w ( l 1 , r 1 ) f ( l 2 , r 2 ) ≤ f ( l 2 , v ) + f ( v + 1 , r 2 ) + w ( l 2 , r 2 ) \begin{cases} f(l_1, r_1) \le f(l_1, u) + f(u + 1, r_1) + w(l_1, r_1) \\ f(l_2, r_2) \le f(l_2, v) + f(v + 1, r_2) + w(l_2, r_2) \end{cases} {f(l1,r1)f(l1,u)+f(u+1,r1)+w(l1,r1)f(l2,r2)f(l2,v)+f(v+1,r2)+w(l2,r2)

    然后由于 u + 1 ≤ v + 1 ≤ r 1 ≤ r 2 u + 1 \le v + 1 \le r_1 \le r_2 u+1v+1r1r2 和我们给出的假设,又可以得到不等式:

    { f ( u + 1 , r 1 ) + f ( v + 1 , r 2 ) ≤ f ( u + 1 , r 2 ) + f ( v + 1 , r 1 ) w ( l 1 , r 1 ) + w ( l 2 , r 2 ) ≤ w ( l 1 , r 2 ) + w ( l 2 , r 1 ) \begin{cases} f(u + 1, r_1) + f(v + 1, r_2) \le f(u + 1, r_2) + f(v + 1, r_1)\\ w(l_1, r_1) + w(l_2, r_2) \le w(l_1, r_2) + w(l_2, r_1) \end{cases} {f(u+1,r1)+f(v+1,r2)f(u+1,r2)+f(v+1,r1)w(l1,r1)+w(l2,r2)w(l1,r2)+w(l2,r1)

    将前两个不等式相加并代入第三个和第四个不等式可以得到:

    f ( l 1 , r 1 ) + f ( l 2 , r 2 ) ≤ f ( l 1 , u ) + f ( l 2 , v ) + f ( u + 1 , r 1 ) + f ( v + 1 , r 2 ) + w ( l 1 , r 1 ) + w ( l 2 , r 2 ) ≤ f ( l 1 , u ) + f ( l 2 , v ) + f ( u + 1 , r 2 ) + f ( v + 1 , r 1 ) + w ( l 1 , r 1 ) + w ( l 2 , r 2 ) ≤ f ( l 1 , u ) + f ( l 2 , v ) + f ( u + 1 , r 2 ) + f ( v + 1 , r 1 ) + w ( l 1 , r 2 ) + w ( l 2 , r 1 ) = [ f ( l 1 , u ) + f ( u + 1 , r 2 ) + w ( l 1 , r 2 ) ] + [ f ( l 2 , v ) + f ( v + 1 , r 1 ) + w ( l 2 , r 1 ) ] = f ( l 1 , r 2 ) + f ( l 2 , r 1 ) \begin{aligned} f(l_1, r_1) + f(l_2, r_2) & \le f(l_1, u) + f(l_2, v) + f(u + 1, r_1) + f(v + 1, r_2) + w(l_1, r_1) + w(l_2, r_2) \\ & \le f(l_1, u) + f(l_2, v) + f(u + 1, r_2) + f(v + 1, r_1) + w(l_1, r_1) + w(l_2, r_2) \\ & \le f(l_1, u) + f(l_2, v) + f(u + 1, r_2) + f(v + 1, r_1) + w(l_1, r_2) + w(l_2, r_1) \\ & = [f(l_1, u) + f(u + 1, r_2) + w(l_1, r_2)] + [f(l_2, v) + f(v + 1, r_1) + w(l_2, r_1)] \\ & = f(l_1, r_2) + f(l_2, r_1) \end{aligned} f(l1,r1)+f(l2,r2)f(l1,u)+f(l2,v)+f(u+1,r1)+f(v+1,r2)+w(l1,r1)+w(l2,r2)f(l1,u)+f(l2,v)+f(u+1,r2)+f(v+1,r1)+w(l1,r1)+w(l2,r2)f(l1,u)+f(l2,v)+f(u+1,r2)+f(v+1,r1)+w(l1,r2)+w(l2,r1)=[f(l1,u)+f(u+1,r2)+w(l1,r2)]+[f(l2,v)+f(v+1,r1)+w(l2,r1)]=f(l1,r2)+f(l2,r1)

    情况(2): u > v u > v u>v。显然有 l 1 ≤ v < r 1 , l 2 ≤ u < r 2 l_1 \le v < r_1, l_2 \le u < r_2 l1v<r1,l2u<r2

    得到不等式组:

    { f ( l 1 , r 1 ) ≤ f ( l 1 , v ) + f ( v + 1 , r 1 ) + w ( l 1 , r 1 ) f ( l 2 , r 2 ) ≤ f ( l 2 , u ) + f ( u + 1 , r 2 ) + w ( l 2 , r 2 ) \begin{cases} f(l_1, r_1) \le f(l_1, v) + f(v + 1, r_1) + w(l_1, r_1) \\ f(l_2, r_2) \le f(l_2, u) + f(u + 1, r_2) + w(l_2, r_2) \end{cases} {f(l1,r1)f(l1,v)+f(v+1,r1)+w(l1,r1)f(l2,r2)f(l2,u)+f(u+1,r2)+w(l2,r2)

    然后根据 l 1 ≤ l 2 ≤ v ≤ u l_1 \le l_2 \le v \le u l1l2vu 和我们的假设得到:

    { f ( l 1 , v ) + f ( l 2 , u ) ≤ f ( l 1 , u ) + f ( l 2 , v ) w ( l 1 , r 1 ) + w ( l 2 , r 2 ) ≤ w ( l 1 , r 2 ) + w ( l 2 , r 1 ) \begin{cases} f(l_1, v) + f(l_2, u) \le f(l_1, u) + f(l_2, v) \\ w(l_1, r_1) + w(l_2, r_2) \le w(l_1, r_2) + w(l_2, r_1) \end{cases} {f(l1,v)+f(l2,u)f(l1,u)+f(l2,v)w(l1,r1)+w(l2,r2)w(l1,r2)+w(l2,r1)

    将两个不等式相加,并将第三个不等式和第四个不等式代入,通过与 情况(1) 相似的变换方法,我们仍然可以得到: f ( l 1 , r 1 ) + f ( l 2 , r 2 ) ≤ f ( l 1 , r 2 ) + f ( l 2 , r 1 ) f(l_1, r_1) + f(l_2, r_2) \le f(l_1, r_2) + f(l_2, r_1) f(l1,r1)+f(l2,r2)f(l1,r2)+f(l2,r1)

    综上,该 引理 得证。


    对于 f ( l , r ) = max ⁡ k = l r − 1 { f ( l , k ) + f ( k + 1 , r ) } + w ( l , r ) f(l, r) = \max\limits_{k = l}^{r - 1}\{f(l, k) + f(k + 1, r)\} + w(l, r) f(l,r)=k=lmaxr1{f(l,k)+f(k+1,r)}+w(l,r) 的情况,只需要将上面的不等式的不等号全部换一个方向就是了。

    Part.1/3 决策单调性的证明

    区间上的决策单调性是指当区间的两个端点中的至少一个向右移动时,其决策点仍在当前位置上或者在当前位置之后。

    定理: 若状态 f ( l , r ) f(l, r) f(l,r) 满足四边形不等式,我们记 p ( l , r ) p(l, r) p(l,r) 为其对应的决策点,则一定存在:

    p ( l , r − 1 ) ≤ p ( l , r ) ≤ p ( l + 1 , r ) p(l, r - 1) \le p(l, r) \le p(l + 1, r) p(l,r1)p(l,r)p(l+1,r)


    证明: 这里以 f ( l , r ) = min ⁡ k = l r − 1 { f ( l , k ) + f ( k + 1 , r ) } + w ( l , r ) f(l, r) = \min\limits_{k = l}^{r - 1} \{f(l, k) + f(k + 1, r)\} + w(l, r) f(l,r)=k=lminr1{f(l,k)+f(k+1,r)}+w(l,r) 为例, f ( l , r ) = max ⁡ k = l r − 1 { f ( l , k ) + f ( k + 1 , r ) } + w ( l , r ) f(l, r) = \max\limits_{k = l}^{r - 1} \{f(l, k) + f(k + 1, r)\} + w(l, r) f(l,r)=k=lmaxr1{f(l,k)+f(k+1,r)}+w(l,r) 可用类似的方法推导。

    这里采用反证法来证明这个结论。

    u = p ( l , r ) , k 1 = p ( l , r − 1 ) , k 2 = p ( l + 1 , r ) u = p(l, r), k_1 = p(l, r - 1), k_2 = p(l + 1, r) u=p(l,r),k1=p(l,r1),k2=p(l+1,r),则我们应该证明: k 1 ≤ u ≤ k 2 k_1 \le u \le k_2 k1uk2。由于证明 k 1 ≤ u k_1 \le u k1u 和证明 u ≤ k 2 u \le k_2 uk2 类似,这里只给出 k 1 ≤ u k_1 \le u k1u 的证明。 u ≤ k 2 u \le k_2 uk2 的部分请读者自行完成

    证明 k 1 ≤ u k_1 \le u k1u 假设有 u < k 1 u < k_1 u<k1,则显然有 u + 1 ≤ k 1 + 1 ≤ r − 1 ≤ r u + 1 \le k_1 + 1 \le r - 1 \le r u+1k1+1r1r

    根据四边形不等式可以得到:
    f ( u + 1 , r − 1 ) + f ( k 1 + 1 , r ) ≤ f ( u + 1 , r ) + f ( k 1 + 1 , r − 1 ) f(u + 1, r - 1) + f(k_1 + 1, r) \le f(u + 1, r) + f(k_1 + 1, r - 1) f(u+1,r1)+f(k1+1,r)f(u+1,r)+f(k1+1,r1)

    又由于 u u u 是区间 [ l , r ] [l, r] [l,r] 的最优决策点,则我们可以得到:

    f ( l , u ) + f ( u + 1 , r ) ≤ f ( l , k 1 ) + f ( k 1 + 1 , r ) f(l, u) + f(u + 1, r) \le f(l, k_1) + f(k_1 + 1, r) f(l,u)+f(u+1,r)f(l,k1)+f(k1+1,r)

    两不等式相加并化简得到:

    f ( l , u ) + f ( u + 1 , r − 1 ) ≤ f ( l , k 1 ) + f ( k 1 + 1 , r − 1 ) f(l, u) + f(u + 1, r - 1) \le f(l, k_1) + f(k_1 + 1, r - 1) f(l,u)+f(u+1,r1)f(l,k1)+f(k1+1,r1)

    不难发现若是这种状态的话区间 [ l , r − 1 ] [l, r - 1] [l,r1] 的决策点应该是 u u u 而不是 k 1 k_1 k1,与假设矛盾,所以必有 k 1 ≤ u k_1 \le u k1u


    这样就有决策单调性了。

    Part.1/4 时间复杂度的证明

    在转移时记录下 p ( l , r ) p(l, r) p(l,r),我们可以将决策点的枚举数量将降为:

    ∑ 1 ≤ l ≤ r ≤ n p ( l + 1 , r ) − p ( l , r − 1 ) = ∑ i = 1 n p ( i , n ) − p ( 1 , i ) ≤ n 2 \sum\limits_{1 \le l \le r \le n} p(l + 1, r) - p(l, r - 1) = \sum\limits_{i = 1}^{n} p(i, n) - p(1, i) \le n^2 1lrnp(l+1,r)p(l,r1)=i=1np(i,n)p(1,i)n2

    所以这样的话时间复杂度就变成了 O ( N 2 ) O(N^2) O(N2)

    Part.1/5 实现方法

    我们可以边转移边记录转移的位置,核心代码如下:

    for(int len = 2; len <= N; len++)
    	for(int i = 1; i <= N - len + 1; i++) {
    		int j = i + len - 1;
    		f[i][j] = INF;
    		for(int k = pos[i][j - 1]; k <= pos[i + 1][j]; k++) {
    			int val = f[i][k] + f[k + 1][j] + calc_cost(i, j);
    			if(val < f[i][j]) f[i][j] = val, pos[i][j] = k;
    		}
    	}
    

    Part.2 其他模型

    如果有我没有找到的模型就在评论区指出一下。

    Part.2/1 一维 DP 模型

    Part2/1-1 模型概述

    将一个由 n n n 个数构成的序列 A i A_i Ai 划分成任意多段,每段的代价为 w ( l , r ) w(l, r) w(l,r)。求最大或者最小代价。

    这类 DP 的状态定义一般为 f ( i ) f(i) f(i) 表示将前 i i i 个数划分成任意段数的代价,则(以最小代价为例,最大代价可同理推出)状态转移方程为:

    f ( i ) = min ⁡ j = 1 i − 1 { f ( j ) + w ( j , i ) } f(i) = \min\limits_{j = 1}^{i - 1}\{f(j) + w(j, i)\} f(i)=j=1mini1{f(j)+w(j,i)}

    Part2/1-2 决策单调性的证明

    我们记 k 1 k_1 k1 f ( i 1 ) f(i_1) f(i1) 的决策点, k 2 k_2 k2 f ( i 2 ) f(i_2) f(i2) 的决策点,则我们应该证明:

    k 1 ≤ k 2 ≤ i 1 ≤ i 2 k_1 \le k_2 \le i_1 \le i_2 k1k2i1i2

    考虑反证法,假设有 k 2 < k 1 < i 1 ≤ i 2 k_2 < k_1 < i_1 \le i_2 k2<k1<i1i2,则根据四边形不等式:

    w ( k 2 , i 1 ) + w ( k 1 , i 2 ) ≤ w ( k 1 , i 1 ) + w ( k 2 , i 2 ) w(k_2, i_1) + w(k_1, i_2) \le w(k_1, i_1) + w(k_2, i_2) w(k2,i1)+w(k1,i2)w(k1,i1)+w(k2,i2)

    又因为 k 2 k_2 k2 i 1 i_1 i1 的最优决策点,所以应该有:

    f ( k 2 ) + w ( k 2 , i 2 ) ≤ f ( k 1 ) + w ( k 1 , i 2 ) f(k_2) + w(k_2, i_2) \le f(k_1) + w(k_1, i_2) f(k2)+w(k2,i2)f(k1)+w(k1,i2)

    两式相加得到:

    f ( k 2 ) + w ( k 2 , i 1 ) ≤ f ( k 1 ) + w ( k 1 , i 1 ) f(k_2) + w(k_2, i_1) \le f(k_1) + w(k_1, i_1) f(k2)+w(k2,i1)f(k1)+w(k1,i1)

    显然不符合 k 1 k_1 k1 i 1 i_1 i1 的最优决策点。这样就有决策单调性了。

    Part2/1-3 实现方法——分治

    由于我们没办法直接确定每个位置的决策点但可以确定它们所在的区间,所以我们用分治来解决。

    void DFS(int lb, int ub, int optl, int optr) {
    	if(lb > ub) return;
    	int mid = (lb + ub) >> 1, pos = optl;
    	f[mid] = calc_cost(pos, mid);
    	for(int i = optl; i <= optr && i <= mid; i++) {
    		int tmp = calc_cost(i, mid);
    		if(tmp < f[mid]) f[mid] = tmp, pos = i;
    	}
    	DFS(lb, mid - 1, optl, pos);
    	DFS(mid + 1, ub, pos, optr);
    }
    

    复杂度为 O ( N log ⁡ 2 N ) O(N \log_2 N) O(Nlog2N)

    Part.2/2 有阶段限制的一维 DP 模型

    Part.2/2-1 模型概述

    将一个由 n n n 个数构成的序列 A i A_i Ai 划分成 k k k 段,每段的代价为 w ( l , r ) w(l, r) w(l,r),满足 w ( l , r ) w(l, r) w(l,r) 满足四边形不等式,求最小或最大代价和。

    这类 DP 的状态定义一般为 f ( i , j ) f(i, j) f(i,j) 表示将前 j j j 个数分成 i i i 段所产生的代价。转移方程式为:(这里仅以最小代价为例,最大代价可类比推出)

    f ( i , j ) = min ⁡ k = 1 j { f ( i − 1 , k − 1 ) + w ( k , j ) } f(i, j) = \min\limits_{k = 1}^{j}\{f(i - 1, k - 1) + w(k, j)\} f(i,j)=k=1minj{f(i1,k1)+w(k,j)}

    Part.2/2-2 证明决策单调性

    其实证明和上面的差不多,只是用到的是上一层的状态罢了。

    p ( i , j ) p(i, j) p(i,j) f ( i , j ) f(i, j) f(i,j) 的最优决策点,我们可以得到结论:

    p ( i − 1 , j ) ≤ p ( i , j ) ≤ p ( i , j + 1 ) p(i - 1, j) \le p(i, j) \le p(i, j + 1) p(i1,j)p(i,j)p(i,j+1)

    Part.2/2-3 实现方法

    Part.2/2-3-1 分治

    知道了决策单调性,我们就可以用分治来乱搞了。

    定义函数 g ( i , l , r , p l , p r ) g(i, l, r, p_l, p_r) g(i,l,r,pl,pr) 表示当前正在划分第 i i i 段,求解 [ l , r ] [l, r] [l,r] 中的状态值,并且已知这些决策点一定位于 [ p l , p r ] [p_l, p_r] [pl,pr] 中的,然后用上面类似的分治算法:

    void DFS(int now, int lb, int ub, int optl, int optr) {
    	if(lb > ub) return;
    	int mid = (lb + ub) >> 1, pos;
    	for(int i = optl; i <= optr && i <= mid; i++) {
    		ll val = f[now - 1][i - 1] + calc_cost(i, mid);
    		if(f[now][mid] > val) f[now][mid] = val, pos = i;
    	}
    	DFS(now, lb, mid - 1, optl, pos);
    	DFS(now, mid + 1, ub, pos, optr);
    }
    
    //主程序内:
    memset(f, 0x3f, sizeof f);
    //尤其注意这句话
    f[0][0] = 0;
    for(int i = 1; i <= K; i++)
    	DFS(i, 1, N, 1, N);
    

    时间复杂度为 O ( K N log ⁡ 2 N ) O(K N \log_2 N) O(KNlog2N),空间复杂度可以用滚动数组优化到 O ( N ) O(N) O(N)

    Part.2/2-3-1 枚举

    注意倒着做就是了。

    for(int i = 0; i <= N; i++)
    	pos[0][i] = 1, pos[i][N + 1] = N;
    //注意这里的神奇初值
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for(int i = 1; i <= K; i++)
    	for(int j = N; j >= 1; j--)
    		for(int k = pos[i - 1][j]; k <= pos[i][j + 1]; k++) {
    			ll val = f[i - 1][k - 1] + c[k][j];
    			if(f[i][j] > val) f[i][j] = val, pos[i][j] = k;
    		}
    

    时间复杂度为 O ( K N ) O(K N) O(KN),空间复杂度为 O ( K N ) O(K N) O(KN)。(不知道可不可以用滚动数组优化一下)

    因为博客太长了,我的 XP 已经卡出了一种境界,所以 Part.3 如何证明 w ( l m r ) w(lm r) w(lmr) 满足四边形不等式Part.4 例题Part.5 参考实现 就放到了下一篇博客去了。

    展开全文
  • 壹:证明cost为凸(满足四边形不等式) 贰:证明dp为凸(满足四边形不等式) 叁:证明决策单调(以找min值为例) ~PART THREE 合并石子问题 第一步(壹)证明cost为凸 第二步(贰)证明dp为凸 第三步(叁)...
  • 四边形不等式优化讲解(详解)

    万次阅读 多人点赞 2017-05-19 08:15:40
    累加器传送门: ... 什么是四边形不等式 S. 四边形不等式优化如何证明 T. 怎么用四边形不等式优化 (感谢博客园的Staginner,他的博客对我有很大影响) 这是他的博客: http://www.cnblogs.com/staginn
  • 看了那么久的四边形不等式优化的原理,今天终于要写一篇关于它的证明了。 在平时的做题中,我们会遇到这样的区间dp问题 它的状态转移方程形式一般为dp[i][j]=min(dp[i][k]+dp[k+1][j]+cost[i][j]);(或者是max...
  • 四边形不等式优化 --算法竞赛专题解析(10)

    千次阅读 多人点赞 2020-03-27 22:59:32
    最全面的四边形不等式DP优化讲解:起源、证明、例题。
  • 首先说明一点,这种方法不是什么题都可以用的,我们要判断DP的情况,看是否能够使用平行四边形不等式来进行优化。一般来说,这种优化还是可以很容易看出来的。 首先两个满足的性质。 四边形不等式 如果有 那么这...
  • 四边形不等式 定义:设\(w(x,y)\)是定义在整数集合上的的二元函数,若对于定义域上的任意整数\(a,b,c,d\),在满足\(a\leq b\leq c \leq d\)时,都有\(w(a,d)+w(b,c)\geq w(a,c)+w(b,d)\)成立,则称函数\(w\)满足...
  •  2、四边形不等式:如果对于 i≤i’≤j’,有 w(i,j)+w(i’,j’)≤w(i’,j)+w(i,j’),我们称函数w满足四边形不等式。(可以形象理解为两个交错区间的w的和不超过小区间与大区间的w的和)    下面给出两个...
  • 都跟j无关了,自然一定满足四边形不等式(这个时候是直接等于了,但没有违反四边形不等式) 第二步(贰)证明dp为凸 要推导dp[i][j]的凸性,自然要满足对任意的i,j,令i  有如下结论  dp[i][j]+dp[i+1][j...
  • 其实这道题本来是要求用斜率优化和四边形不等式优化的... 但是我硬生生做成了决策单调性给交上去了哈哈哈哈...老师应该不会查水表的吧(大雾 题目 1S/128MB M T. E. 劳伦斯是第一次世界大战中饱受争议的人物。他...
  • 四边形不等式优化dp专题
  • 四边形不等式 假如对于任意 a≤b≤c≤da\leq b\leq c\leq da≤b≤c≤d,满足 w(a,c)+w(b,d)≤w(b,c)+w(a,d)w(a,c)+w(b,d)\leq w(b,c)+w(a,d)w(a,c)+w(b,d)≤w(b,c)+w(a,d),那么称 www 满足四边形不等式。...
  • 四边形不等式应用

    2020-01-10 13:18:44
    动态规划加速原理之四边形不等式 动态规划的四边形不等式优化是对特定形式的状态转移方程进行优化的一种方法,该方法可以将复杂度由 O(n3)O(n^3)O(n3) 优化到 O(n2)O(n^2)O(n2)。 设我们有状态转移方程 m(i,j)={min{...
  • 什么是四边形不等式 S. 四边形不等式优化如何证明 T. 怎么用四边形不等式优化 (好气啊,这篇博文我写了两遍,第一遍的没有保存就关了) (感谢博客园的Staginner,他的博客对我有很大影响) (感谢wys大佬亲自为...
  •  顺便提到一件事,最优矩阵链乘问题(MCM)的dp方法,是没有办法采用四边形不等式优化的,原因是递推式的权值项不仅和i,j有关,还和k有关系。但是MCM问题是有非dp解法的,可以达到O(nlogn),参见 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,291
精华内容 1,716
关键字:

四边形不等式