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

    2021-05-28 15:13:23
    可以通过四边形不等式优化该方程,可将时间复杂度O(N ^ 3)优化至O(N ^ 2) 先抛出两个概念 1. 区间单调性 若满足 a <= b <= c <= d,且 w[b][c] <= w[a][d]。那么w具有区间单调性。 2. 四边形不等式 若

    当你遇到这样的转移方程:dp[i][j] = min(dp[i][k-1], dp[k][j]) + w[i][j] 且n较大时。。。
    低情商:无脑三层 for,喜提 TLE (暴力美学)
    高情商:这不是有手题??? (四边形不等式优化)

    虽然它俩都是三层for,但是后者的复杂度却只有O(N^2),这就是四边形不等式能干的事。

    先放结论:

    形如 dp[i][j] = min(dp[i][k-1], dp[k][j]) + w[i][j],其中 i <= k <= j,dp[i][j]表示区间i到j上的最值(此处以最小值为例,也可以为最大值)。
    可以通过四边形不等式优化该方程,可将时间复杂度O(N ^ 3)优化至O(N ^ 2)

    先抛出两个概念

    1. 区间单调性

    若满足 a <= b <= c <= d,且 w[b][c] <= w[a][d]。那么w具有区间单调性。
    在这里插入图片描述

    2. 四边形不等式

    若满足 a <= b <= c <= d,且 w[a][c] + w[b][d] <= w[a][d] + w[b][c] 。那么w满足四边形不等式。

    在这里插入图片描述




    接着引入一个数组 s[i][j] ,表示dp[i][j] 取得最优值时对应的下标
    再来两个性质:

    1. 若 w[ ][ ] 同时满足上面提到的区间单调性四边形不等式,则 dp[ ][ ] 满足四边形不等式。
    2. dp[i][j] 满足四边形不等式,则 s[i][j] 单调,即 s[i][j-1] ≤ s[i][j] ≤ s[i+1][j]

    那么,现在的问题就成了求 s[ ][ ]。而根据 s[ ][ ] 的定义,应该不难求出来。


    看到这里应该有想法了吧?且往下看


    原本暴力的循环 ↓

    for (int j = 1; j <= n; j++) 
      for (int i = j; i >= 1; i--) 
        for (int k = i; k < j; k++) 
          dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);
    

    四边形不等式优化 ↓

    for (int j = 1; j <= n; j++) 
      for (int i = j; i >= 1; i--) 
    	for (int k = s[i][j-1] ; k <= s[i+1][j] ; k++) {
    	  if(dp[i][j] > dp[i][k]+dp[k+1][j]+w[i][j]) {
    	    dp[i][j] = dp[i][k]+dp[k+1][j]+w[i][j];
    	    s[i][j] = k;
    	  }
    	}
    

    为啥这样能做到O(N^2)呢?
    这是因为枚举的区间长度 len = j-i,而 s[i,j-1] 和 s[i+1,j] 的长度是 len-1,是上一次已经计算过的,可以直接调用,所以时间复杂度为 O(N^2)。

    —end—

    展开全文
  • 大概大一下学期还是啥时候就听说过这个优化了。现在都大三下了才正式开始学这东西,哈哈,太垮了.这里只记录结论和如何使用。不说证明(也看不懂. 1.使用场合: 优化转移: 1.dp(i,j)=min{dp(i,k)+dp(k,j)+w(i,j)}dp(i...

    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;
    }
    
    展开全文
  • 四边形不等式优化讲解(详解)

    万次阅读 多人点赞 2017-05-19 08:15:40
    累加器传送门: ... 本篇博文意在详细讲解如下内容... 四边形不等式优化如何证明 T. 怎么用四边形不等式优化 (感谢博客园的Staginner,他的博客对我有很大影响) 这是他的博客: http://www.cnblogs.com/staginn

    累加器传送门:

    http://blog.csdn.net/NOIAu/article/details/71775000


    本篇博文意在详细讲解如下内容

    F. 什么是四边形不等式

    S. 四边形不等式优化如何证明

    T. 怎么用四边形不等式优化

    (好气啊,这篇博文我写了两遍,第一遍的没有保存就关了)
    (感谢博客园的Staginner,他的博客对我有很大影响)
    (感谢wys大佬亲自为我查了一部分内容的错)
    (如果本文有什么错误的话,请向我提出,非常感谢)
    这是他的博客:
    http://www.cnblogs.com/staginner/archive/2012/03/12/2391925.html


    引入:

    在dp问题中,我们经常遇见这样的一类问题
    他们的dp转移方程是这样的

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

    显然for一边i,for一边j,在算dp[i][j]的时候还得for一遍k,这是O(n^3)的复杂度,这样的复杂度在很多时候是不能接受的,如果dp转移方程已经设计好了,也无法再在dp方程上优化,我们怎么来提高计算效率呢?(关于O(n^2)复杂度的证明我放在最后)


    ~PART ONE 交叉小于包含

    对于( a < b <= c< d )

    如果有f[a][c]+f[b][d]<=f[b][c]+f[a][d]

    (可以理解为一句话,交叉小于包含,即交叉的两个区间,a到c和b到d的值满足小于等于包含的两个区间[bc包含于ad])
    则说这个东西满足四边形不等式,当然这个东西可能是dp数组,也可以是其他数组,比如引入里提到的cost数组,表示的是i到j的花费(比如合并石子问题)

    给出两个定理:

    1、如果上述的w函数同时满足区间包含单调性和四边形不等式性质,那么函数dp也满足四边形不等式性质
    我们再定义s(i,j)表示 dp(i,j) 取得最优值时对应的下标(即 i≤k≤j 时,k 处的 dp 值最大,则 s(i,j)=k此时有如下定理
    2、假如dp(i,j)满足四边形不等式,那么s(i,j)单调,即 s(i,j)≤s(i,j+1)≤s(i+1,j+1)
    如果不知道为什么,没有关系,反正后面都要证明


    ~PART TWO 证明过程三步走

    (这一部分如果没有完全懂没有关系,PART-THREE里会结合题目来推导一遍,所以有一小部分推导在这里先不写出来,这一部分尽量先说原理和方法)


    壹:证明cost为凸(满足四边形不等式)

    显然,当且仅当对于所有的i,j,均满足如下式子
    (令i< i+1<= j< j+1)
    cost[i][j]+cost[i+1][j+1]<=cost[i][j+1]+cost[i+1][j]
    (利用PART ONE的交叉小于包含写出来的式子)
    转移一下式子
    即要证明对于所有的i,j,要使
    cost[i][j]-cost[i+1][j]<=cost[i][j+1]-cost[i+1][j+1]
    试想一个函数f(j)=cost[i][j]-cost[i+1][j],那么要证明这个四边形不等式成立,也就是要证明这个函数f(j)单调递增嘛


    贰:证明dp为凸(满足四边形不等式)

    显然我们需要证明对于任意的i,j
    i< i+1<= j< j+1
    均满足
    dp[i][j]+dp[i+1][j+1]<=dp[i+1][j]+dp[i][j+1]
    这一步其实是建立在的上面的,可以用的结论来推导贰的结论
    假设式子右边的dp[i+1][j]取得最优值的时候的k为x(之前不是要for一遍k来寻找最优时候的解嘛),右边式子里的dp[i][j+1]取得最优值的时候的k为y,这个时候把k=x带入左式的dp[i][j]中,把k=y带入左式的dp[i+1][j+1]中,然后寻找dp数组和cost数组的联系,把左边的式子配凑出右边的式子然后完成证明
    (可能看不懂这句话是什么意思,不是很擅长表达,具体的证明方式大家可以结合PART-THREE里详细论证过程来学习,如果没懂就很不舒服的,现在就可以结合PART THREE看啦)


    叁:证明决策单调(以找min值为例)

    如果我们用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]来说,我们先令dp[i][j-1]取得最优解的时候的k值为y,然后令除了最优值以外的其他值可以为x,这里我们由于要讨论单调性,所以让x小于y,即x<=y<=j-1< j
    然后利用我们在壹和贰里已经证明了的结论,来列一个关于dp数组的四边形不等式,然后在两边同时加上cost数组以求拼凑出如下的结论
    dp[i][j-1] (k=x)+dp[i][j] (k=y)<=dp[i][j-1] (k=y)+dp[i][j] (k=x)
    ( 这个看起来也有点奇怪,不过PART-THREE会讲具体是怎样操作的 )
    然后进行移项
    dp[i][j-1] (k=x)-dp[i][j-1] (k=y)<=dp[i][j] (k=x)-dp[i][j] (k=y)
    可以这样理解
    我们之前是令dp[i][j-1]取得最优值的时候k=y,所以对于所有的x小于y,一定有dp[i][j-1](k=x)>=dp[i][j-1] (k=y)(因为我们这里最优值是指最小值),所以很自然的,dp[i][j] (k=x)-dp[i][j] (k=y)也必然会大于等于零,也就是说,有如下结论
    dp[i][j] (k=x)>=dp[i][j] (k=y)
    什么意思呢,让dp[i][j-1]可以取得最小值的y,对于dp[i][j]的决策来说,可以使得所有小于y的x的值都没有y优,所以dp[i][j]的最优决策一定不会小于y,所以如果我们用s[i][j]表示dp[i][j]取得最优值的时候的k值,那么一定有
    s[i][j-1]<=s[i][j]
    而s[i][j]<=s[i+1][j]的证明是类似的,读者可以自己再推一遍


    ~PART THREE

    终于到了激动人心的详细证明过程和如何使用四边形不等式进行优化,亦可赛艇!
    看例题来讲解总是好的,这里我们就举一个大家都做过的广为熟知的题


    合并石子问题

    现在有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数组是前缀和
    for一遍i,for一遍j,每算一次dp[i][j]还要for一遍k,自然是O(n^3)方,现在我们来按照规则判断是否可以用四边形优化


    第一步(壹)证明cost为凸

    对于所有的i,j,令其满足i< i+1<=j< j+1
    我们需要证明
    cost[i][j]+cost[i+1][j+1]<=cost[i+1][j]+cost[i][j+1]
    移项
    cost[i][j]-cost[i+1][j]<=cost[i][j+1]-cost[i+1][j+1]
    令f(j)=cost[i][j]-cost[i+1][j]
    f(j)=cnt[j]-cnt[i-1]-(cnt[j]-cnt[i])
    f(j)=cnt[i]-cnt[i-1]
    都跟j无关了,自然一定满足四边形不等式(这个时候是直接等于了,但没有违反四边形不等式)


    第二步(贰)证明dp为凸

    要推导dp[i][j]的凸性,自然要满足对任意的i,j,令i< i+1<=j< j+1
    有如下结论
    dp[i][j]+dp[i+1][j+1]<=dp[i+1][j]+dp[i][j+1]
    令dp[i+1][j]取得最优值的时候k=x
    令dp[i][j+1]取得最优值的时候k=y
    令x < =y(之后还要令x > y,这里不再赘述,读者如有兴趣可以自行推导,方式相似)
    将k=x代入dp[i][j],k=y代入dp[i+1][j+1]
    左式=dp[i][x]+dp[x+1][j]+cost[i][j]+dp[i+1][y]+dp[y+1][j+1]+cost[i+1][j+1]①
    而对于i< i+1<=j< j+1
    由于已经在壹中证明了cost的凸性,所以
    cost[i][j]+cost[i+1][j+1]<=cost[i+1][j]+cost[i][j+1]②
    我们会发现这个不等式的左边在①式中出现过,所以把②式中的左式和右式替换一下可以得到如下结论
    dp[i][x]+dp[x+1][j]+cost[i][j]+dp[i+1][y]+dp[y+1][j+1]+cost[i+1][j+1]
    <=

    dp[i][x]+dp[x+1][j+1]+cost[i][j+1]+dp[i+1][y]+dp[y+1][j]+cost[i+1][j]

    即dp[i][j]+dp[i+1][j+1]<=dp[i][j+1]+dp[i+1][j]
    证毕


    第三步(叁)证明决策单调

    现在我们已经证明了cost数组和dp数组的凸性,要证明决策单调以证明优化的正确性
    即要证明s[i][j-1]<=s[i][j]<=s[i+1][j]
    对于s[i][j-1]<=s[i][j]
    令dp[i][j-1]取得最小值时的k=y,对于所有x≠y,令x<=y
    可以有如下推导
    ∵x+1<=y+1<=j-1< j
    四边形不等式有:
    dp[x+1][j-1]+dp[y+1][j]<=dp[y+1][j-1]+dp[x+1][j]

    在式子两边同时加上dp[i][x]+cost[i][j-1]+dp[i][y]+cost[i][j] 可以得到

    dp[i][x]+dp[x+1][j-1]+cost[i][j-1]+dp[i][y]+dp[y+1][j]+cost[i][j]
    <=
    dp[i][x]+dp[x+1][j]+cost[i][j]+dp[i][y]+dp[y+1][j-1]+cost[i][j-1]

    dp[i][j-1]+dp[i][j]<=dp[i][j]+dp[i][j-1]
    (k=x)…………(k=y)……(k=x)……(k=y)
    移项

    dp[i][j-1]-dp[i][j-1]<=dp[i][j]-dp[i][j]
    (k=x)…………(k=y)……(k=x)……(k=y)

    由于我们是令k=y时dp[i][j-1]取得最小值,那么dp[i][j-1] (k=x)一定大于等于dp[i][j-1] (k=y),所以左式大于零,所以右式也大于零,所以对于dp[i][j-1]可以取到最优值的y,所有小于它的值,对于dp[i][j]来说,都没有y优,所以最优决策一定不是小于y的,如果令s[i][j]表示dp[i][j]取得最优值的时候的k值,那么一定有
    s[i][j-1]<=s[i][j]
    证毕
    对于不等式后半部分的证明类似,读者有兴趣可以自己再证明一次


    代码如下

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #define MAXN 10000+10
    using namespace std;
    
    int dp[MAXN][MAXN],s[MAXN][MAXN],cnt[MAXN];
    int n;
    
    void init(){
        scanf("%d",&n);
        for(register int i=1;i<=n;i++) scanf("%d",&cnt[i]),cnt[i]=cnt[i-1]+cnt[i];
        for(register int i=1;i<=n;i++){
            dp[i][i]=0;s[i][i]=i; 
        }
        for(register int i=n;i>=1;i--){
            for(register int j=i+1;j<=n;j++){
                int temp=0x7fffffff;
                int te;
                for(int k=s[i][j-1];k<=s[i+1][j];k++){
                    if(temp>dp[i][k]+dp[k+1][j]+cnt[j]-cnt[i-1]){
                        temp=dp[i][k]+dp[k+1][j]+cnt[j]-cnt[i-1];
                        te=k;
                    }
                }
                dp[i][j]=temp;
                s[i][j]=te;
            }
        }
    }
    
    void print(){
        cout<<dp[1][n]<<endl;
    }
    
    int main(){
        init();
        print();
    }

    尤其要注意for的顺序,因为我们在推dp[i][j]的时候要用s[i][j-1]和s[i+1][j]所以i一定是倒序的,这样才能在求dp[i][j]的时候调用dp[i+1][j]的最优决策s[i+1][j],而j一定是顺序的,这样才能在求dp[i][j]的时候调用dp[i][j-1]的最优决策s[i][j-1]


    关于O(n^2)复杂度的证明

    其实证明很简单,对于一个i,j来说,我们要for s[i][j-1]到s[i+1][j]个数,那么所有的i和j加起来一共会for多少次呢?
    我们可以这样思考
    (s[2][2]-[1][1])+(s[3][3]-s[2][2])+(s[4][4]-s[3][3])+…+(s[n][n]-s[n-1][n-1])=s[n][n]-s[1][1]很显然是小于n的嘛,所以本来是(n *n *n)的复杂度,就这样降成了O(n *n)啦


    最后说一句

    对于dp转移合法的证明,其实很多时候我们不用像我写的这样去判断,直接打表就行了,比如先跑一个O(n^3)的代码,跑的时候判断是否满足四边形不等式,决策是否单增等等,如果不满足就输出false之类的,或者打一个决策表出来观察,这样其实会省下一部分时间,之前的所有证明,只是帮助你理解该算法(该优化)的正确性


    附加习题:

    No.1 Hdu 3480
    http://blog.csdn.net/noiau/article/details/72533326
    No.2 Hdu 2829
    http://blog.csdn.net/noiau/article/details/72529185
    No.3 Hdu3516
    http://blog.csdn.net/noiau/article/details/72525936
    No.4 POJ 1160
    http://blog.csdn.net/noiau/article/details/72550871

    展开全文
  • 其实这道题本来是要求用斜率优化和四边形不等式优化的... 但是我硬生生做成了决策单调性给交上去了哈哈哈哈...老师应该不会查水表的吧(大雾 题目 1S/128MB M T. E. 劳伦斯是第一次世界大战中饱受争议的人物。他...

    前言

    其实这道题本来是要求用斜率优化和四边形不等式优化的...

    但是我硬生生做成了决策单调性给交上去了哈哈哈哈...老师应该不会查水表的吧(大雾

    题目

    1S/128MB

    M T. E. 劳伦斯是第一次世界大战中饱受争议的人物。他是一名在阿拉伯战区服役 的英国军官,率领着一群阿拉伯人对奥图曼帝国开展游击战。他袭击的主要目标 是铁路。有关劳伦斯的虚构功绩反映在一部大制作电影“阿拉伯的劳伦斯”中。 请你写一个程序帮助劳伦斯计算出怎样最优化地利用他有限的资源。你有一些英国情报部门提供的信息。

    首先,铁路线是完全线性的,即没有任何分支和岔道。 其次, 英国情报部门对每个车站标记了战略价值——即一个 1~5 之间的整数。

    一条铁路线的战略总价值是所有相邻两个车站的战略价值乘积之和。

    例如下图:

    这条铁路线的战略总价值为: 4*5 + 4*1 + 4*2 + 5*1 + 5*2 + 1*2 = 49

    假设劳伦斯只有发动一次袭击的战斗资源,而且他不可能去袭击车站,因为车站 的防守是非常坚固的。他只能去袭击车站之间的铁路线。

    例如,劳伦斯选择去袭 击中间的铁路线:

    那么剩下的战略价值为 4*5 + 1*2 = 22

    但如果劳伦斯去袭击 4 和 5 之间的铁路线:

    那么剩下的战略价值为 5*1 + 5*2 + 1*2 = 17

    这是劳伦斯最佳的选择。

    给出铁路线的描述和劳伦斯能发动袭击的次数, 计算出能获得的最小的战略总价值。
    Input

    有多组测试数据,每组数据格式为:

    第 1 行: 2 个整数: n (1≤n≤1000)表示车站的个数, m (0≤m<n)表示袭击的次数。

    第 2 行: n 个整数, 每个数在 1~5 之间,表示按顺序排列的 n 个车站的战略价 值。

    最后一行 n=0 且 m=0, 表示数据结束。
    Output

    对每组数据,在一行上仅输出一个整数,表示最小的战略总价值。
    Sample Input

    4 1

    4 5 1 2

    4 2

    4 5 1 2

    0 0
    Sample Output

    17

    2

    分析

    经观察可发现本题——还是很“板”(2333)

    与这道题差不多:监狱警卫

    本质上还是【分组\分段+计算花费】

    可以写出DP定义与转移方程:

    dp[ i ][ j ]:1~j个车站分成i段

    对于最后一段i,假设从第k到j的车站铁路为最后第i段

    dp[ i ][ j ]=min( dp[ i ][ j ],dp[ i-1 ][ k-1 ]+cost( k , j );

    初始化:dp[ 1 ][ 1~n ]=INF

    关于【cost的计算】——哇,哭了,居然考数学功底...

    我们发现,任意一段区间a1,a2……ai的权值可以这么计算:

    s=(a1a2+……+a1ai)+(a2a3+……+a2ai)+……=[(a1+a2+……+ai)^2−(a1^2+a2^2+……+ai^2)]/2

    也就是(这一段sum的平方-这一段各数平方之和)/2。

    前缀和分别预处理即可

    然后直接套用【决策单调性分治优化】或【四边形不等式优化】即可,详见代码

    Ps.本题只要求了【最多炸m次】,即【最多分成m+1段】,并没有严格限制,所以最后统计答案的时候要从分1~m+1段中取最小值

    决策单调性分治优化-代码

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const ll MAXN=1000,INF=0x3f3f3f3f;
    ll a[MAXN+5],dp[MAXN+5][MAXN+5],pre[MAXN+5],s[MAXN+5];
    ll n,m,ans=INF;
    void DP(ll d,ll i,ll j,ll optl,ll optr)//决策优化 
    {
    	if(i>j)
    		return ;
    	ll mid=(i+j)/2;
    	ll opt=INF,id;
    	//暴力计算二分点的dp值opt与最小决策点id 
    	for(int k=optl;k<=min(optr,mid);k++)
    	{
    		ll cur=dp[d-1][k-1]+((pre[mid]-pre[k-1])*(pre[mid]-pre[k-1])-(s[mid]-s[k-1]))/2;
    		if(cur<opt)
    			opt=cur,id=k;
    	}
    	dp[d][mid]=opt;
    	//递归求解决策点左右两部分的dp值 
    	DP(d,i,mid-1,optl,id);
    	DP(d,mid+1,j,id,optr);
    } 
    void Solve()
    {
    	for(int i=1;i<=n;i++)
    		dp[0][i]=INF;
    	for(int i=1;i<=m;i++)
    		DP(i,1,n,1,n);
    	for(int i=1;i<=m;i++)
    		ans=min(ans,dp[i][n]);
    	printf("%lld\n",ans);
    }
    int main()
    {
    	while(~scanf("%lld%lld",&n,&m))
    	{
    		if(!n&&!m)
    			break;
    		m++;//至多炸m个,即之多分成m+1段 
    		for(int i=1;i<=n;i++)
    		{
    			scanf("%lld",&a[i]);
    			pre[i]=pre[i-1]+a[i];
    			s[i]=s[i-1]+a[i]*a[i];
    		}
    		Solve();
    	}
    	return 0;
    }

    四边形不等式优化-代码

    咕咕

    展开全文
  • 然后直接套用【决策单调性分治优化】或【四边形不等式优化】即可,详见代码 决策单调性分治优化-代码(含暴力DP) #include #include #include #include #include using namespace std; typedef long long ...
  • 四边形不等式 定义:设\(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\)满足...
  • 四边形不等式优化dp专题
  •  下面我们通过四边形不等式优化上述方程,首先介绍什么是“区间包含的单调性”和“四边形不等式”  1、区间包含的单调性:如果对于 i≤i’≤j’,有 w(i’,j)≤w(i,j’),那么说明w具有区间包含的单调性。...
  • 这大概是跟斜率优化一样神的东西qwq,但是证明复杂一点,以及似乎用到的题目也少一点,毕竟使用条件有点苛刻。 正题 它用来加速类似这样的 dpdpdp:f[i][j]=min⁡k=ij−1{f[i][k]+f[k+1][j]+w(i,j)}f[i][j]=\min_{k=...
  • 形式1随手来一个dp式,f[i,j]=min{f[i,k−1]+f[k,j]}f[i,j]=min\{f[i,k-1]+f[k,j]\},谁来说说这个dp...引入——四边形不等式内容:∀a≤b≤c≤d\forall a \le b \le c \le d,若ww满足 w[a,c]+w[b,d]≤w[a,d]+w[b,c]
  • 四边形不等式优化dp

    2018-04-19 11:43:52
    这时候我们就要用到四边形不等式优化dp啦 二、四边形不等式 如果有一个矩阵 M M M ,对于任意 a < b , c < d a < b , c < d a,c ,有 M ( a , c ) + M ( b , d ) ≥ M ( a , d ) + M ( b , c ) M ( a , c ) + ...
  • 那么代入转移方程中,移一下项,可以斜率优化,也可以四边形优化。 注意这是二维的斜率优化,要注意更新的是哪个j对应的队列。 AC代码 //HDU- 2829 Lawrence //AC 2017 - 2 - 26 15 : 10 : 03 //DP,...
  • 很久以前做过一个环形石子归并的题目,因为数据较大、复杂度较高,O(n3)O(n3)O(n^3),所以 TLETLETLE 了,需要用到四边形不等式优化一下,几乎降低复杂度到 O(n2)O(n2)O(n^2),才能 ACACAC。 我们先来看一下这个...
  • Strategy:区间dp(用四边形不等式优化) 先贴一波大佬的博客 若想用四边形不等式优化必须满足 决策单调性 , 就本题而言, 针对dpmin[i][j]都有某最K值使得该最小值被取到, 而且, 该最小值是和决策区间[i][j]有非...
  • 写在前面 考试的时候遇到了还是直接套定理然后对拍吧 学习资料 四边形不等式优化讲解(详解) By NOIAu 石子合并的题解 例题 石子合并 链接:
  • 四边形不等式优化_石子合并问题_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...
  • *令p[i][j]表示使得f[i][j]最小的那个k,根据四边形不等式优化可知p[i-1][j][i][j][i][j+1] */ void work() { cin >> n >> m; for (int i = 1; i ; i++) cin >> x[i]; for (int i = 1; i ; i++) { ...
  • 例题:Division HDU - 3480 区间dp 与 四边形不等式优化 或者 斜率优化 形如: dp[i][j]=min{dp[i][k]+dp[k+1][j]+cost[i][j]} 的状态转移方程,如果不加优化的话ijk三层循环O(n^3)的复杂度是难以接受的。考虑四....
  • 壹:证明cost为凸(满足四边形不等式) 贰:证明dp为凸(满足四边形不等式) 叁:证明决策单调(以找min值为例) ~PART THREE 合并石子问题 第一步(壹)证明cost为凸 第二步(贰)证明dp为凸 第三步(叁)...
  • 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...
  • / # 四边形不等式学习笔记四边形不等式学习笔记四边形不等式学习笔记 四边形不等式的定义四边形不等式的定义四边形不等式的定义 摘自 lyd′slyd'slyd′s bookbookbook 定义一定义一定义一 定义 w...
  • 的状态i需要从前面(0~i-1)个状态找出最优子决策做转移时 我们常常需要双重循环(一重循环跑状态 i,一重循环跑 i 的所有子状态)这样的时间复杂度是O(N^2)而 斜率优化或者四边形不等式优化后的DP可以将时间复杂度...

空空如也

空空如也

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

四边形不等式优化