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

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

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

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

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

    前置芝士:

    四边形不等式的定义:

    对于定义域为 I I I的二元函数 w ( i , j ) w(i,j) w(i,j),若满足 ∀ a < b < c < d ∈ I , 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) a<b<c<dI,w(a,c)+w(b,d)w(a,d)+w(b,c)则称函数 w w w满足四边形不等式

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

    ∀ a < b ∈ I , 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) a<bI,w(a,b)+w(a+1,b+1)w(a+1,b)+w(a,b+1)

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

    决策单调性的定义是:

    p i p_{i} pi是形如 f i = m a x 0 ≤ j < i ( f j + v a l ( j , i ) ) f_{i}=max_{0\leq j <i}(f_{j}+val(j,i)) fi=max0j<i(fj+val(j,i))的方程取到最佳决策时的 j j j

    我们要证的是:

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

    p [ i ′ ] ≥ p [ i ] p[i'] \geq p[i] p[i]p[i]

    只需证:

    f i + v a l ( p [ i ] , i ′ ) ≤ f j + v a l ( j , i ′ ) , ∀ j ∈ [ 1 , p [ i ] ) f_{i}+val(p[i],i') \leq f_{j}+val(j,i') , \forall j \in [1,p[i]) fi+val(p[i],i)fj+val(j,i),j[1,p[i]) ( 1.1 ) (1.1) (1.1)

    我们得到上述不等式即可

    考虑构造四边形不等式:

    c o s t ( j , i ′ ) + c o s t ( p [ i ] , i ) ≥ c o s t ( j , i ) + c o s t ( p [ i ] , i ′ ) cost(j,i')+cost(p[i],i) \geq cost(j,i)+cost(p[i],i') cost(j,i)+cost(p[i],i)cost(j,i)+cost(p[i],i)

    移项:

    c o s t ( j , i ′ ) − c o s t ( j , i ) ≥ c o s t ( p [ i ] , i ′ ) − c o s t ( p [ i ] , i ) cost(j,i')-cost(j,i) \geq cost(p[i],i')-cost(p[i],i) cost(j,i)cost(j,i)cost(p[i],i)cost(p[i],i) ( 1.2 ) (1.2) (1.2)

    由题设出发有:

    f i + c o s t ( p [ i ] , i ) ≤ f i + c o s t ( j , i ) , ∀ j ∈ [ 1 , p [ i ] ) f_{i}+cost(p[i],i) \leq f_{i}+cost(j,i),\forall j \in [1,p[i]) fi+cost(p[i],i)fi+cost(j,i),j[1,p[i]) ( 1.3 ) (1.3) (1.3)

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

    f i + v a l ( p [ i ] , i ′ ) ≤ f j + v a l ( j , i ′ ) , ∀ j ∈ [ 1 , p [ i ] ) f_{i}+val(p[i],i') \leq f_{j}+val(j,i') , \forall j \in [1,p[i]) fi+val(p[i],i)fj+val(j,i),j[1,p[i])

    ( 1.1 ) (1.1) (1.1)

    证毕.

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

    千次阅读 2018-10-12 13:51:08
    这是使用四边形不等式优化的前题,只有先证明它满足这个条件才可以使用(一般用数学归纳法证明四边形不等式证明(这里以求min为例): 证明 s[i, j - 1] ≤ s[i, j] ≤ s[i + 1, j] 设 d = s[i, j] i +...

    ps:本人小白,文章可能存在错误,希望大佬谅解或指出错误

    先来看一道常规的区间dp,在这里以石子合并为例题

    题目描述:

    有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆。求出总的代价最小值。

    输入

    有多组测试数据,输入到文件结束。
    每组测试数据第一行有一个整数n,表示有n堆石子。
    接下来的一行有n(0< n <200)个数,分别表示这n堆石子的数目,用空格隔开

    输出

    输出总代价的最小值,占单独的一行

    样例输入

    3
    1 2 3
    7
    13 7 8 16 21 4 18

    样例输出

    9
    239

    先来个朴素版本的:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 205;
    int n, x;
    int sum[maxn];
    int dp[maxn][maxn];
    int main()
    {
        while(~scanf("%d",&n))
        {
            sum[0] = 0;
            memset(dp, 0x3f, sizeof(dp));
            for(int i = 1;i <= n;i ++)
            {
                scanf("%d", &x);
                sum[i] = sum[i - 1] + x;
                dp[i][i] = 0;
            }
            for(int len = 2;len <= n;len ++)
            for(int i = 1;i <= n;i ++)
            {
                int j = i + len - 1;
                if(j > n) continue;
                for(int k = i;k < j;k ++)
                {
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j] + sum[j] - sum[i-1]);
                }
            }
            printf("%d\n", dp[1][n]);
        }
        return 0;
    }
    

    其中的区间dp算法不必说,是O(n^3)的。那么能不能优化呢,肯定是可以的,这就是要说的四边形不等式优化。社s[i, j]是 i 到 j 的最佳分割点,由四边形不等式我们可以得知第三重循环寻找最佳分割点的范围就可以从(i, j)压缩到(s[i, j - 1], s[i + 1, j]),这样就可以优化到O(n^2)。代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 205;
    int n,x;
    int sum[maxn];
    int dp[maxn][maxn];
    int s[maxn][maxn];
    int main()
    {
        while(~scanf("%d",&n))
        {
            sum[0] = 0;
            memset(dp, 0x3f, sizeof(dp));
            for(int i = 1;i <= n;i ++)
            {
                scanf("%d",&x);
                sum[i] = sum[i-1] + x;
                dp[i][i] = 0;
                s[i][i] = i;
            }
            for(int len = 2;len <= n;len ++)
            for(int i = 1;i <= n;i ++)
            {
                int j = i + len - 1;
                if(j > n) continue;
                for(int k = s[i][j-1];k <= s[i+1][j];k ++)
                {
                    if(dp[i][k] + dp[k + 1][j] + sum[j] - sum[i-1] < dp[i][j])
                    {
                        dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
                        s[i][j] = k;
                    }
                }
            }
            printf("%d\n",dp[1][n]);
        }
        return 0;
    }
    

     

    我们先来了解一下四边形不等式

    设m[i,j]表示动态规划的状态量(就是i -> j 的最优解)

    m[i,j]有类似如下的状态转移方程:

    m[i,j]=opt{m[i,k]+m[k,j]}(i≤k≤j)

    如果对于任意的a≤b≤c≤d,有m[a,c]+m[b,d]≤m[a,d]+m[b,c],那么m[i,j]满足四边形不等式。

    这是使用四边形不等式优化的前题,只有先证明它满足这个条件才可以使用(一般用数学归纳法证明)

    四边形不等式的证明(这里以求min为例):

    证明 s[i, j - 1] ≤ s[i, j] ≤ s[i + 1, j]

    设 d = s[i, j]         i + 1 ≤ k < d       (d代表 i 到 j 的最优分割点)

    显然   m_{k}[i, j] = m[i, k] + m[k, j]

              m_{d}[i, j] = m[i, d] + m[d, j]

        且   m_{k}[i, j] \geq m_{d}[i, j]              (m[i, j] 在 d 取到最小值)

    构造一个原式:

               (m_{k}[i + 1, j] - m_{d}[i + 1, j]) - (m_{k}[i, j] - m_{d}[i, j])

           =  (m_{k}[i + 1, j] + m_d[i, j]) - (m_{d}[i + 1, j] + m_{k}[i , j])

           =   (m[i + 1, k] + m[k, j] + m[i, d] + m[d, j]) - (m[i +1, d] + m[d, j] + m[i, k] + m[k, j])

           =   (m[i +1, k] + m[i, d]) - (m[i + 1] + m[i, k])

    ∵ m 满足四边形不等式

    ∴ 对于 i < i + 1 ≤ k < d     则有:

                  m[i, k] + m[i + 1, d] \leq m[i + 1, k] + m[i, d]

    带入原式可得

                   (m_{k}[i + 1, j] - m_{d}[i + 1, j]) \geq (m_{k}[i, j] - m_{d}[i, j])

     ∵            (m_{k}[i, j] - m_{d}[i, j]) \geq 0

     ∴            (m_{k}[i + 1, j] - m_{d}[i + 1, j])\geq 0

    ∴             m_{k}[i + 1, j] \geq m_{d}[i + 1, j]

    设             b = s[i + 1, j]                  (b 是i + 1 到 j 上的最优分割点)

    则有          m_{k}[i + 1, j] \geq m_{d}[i + 1, j] \geq m_{b}[i + 1, j]      

                  (ps: 意思就是说在[i + 1, j] 上存在 b 使得 m[i + 1, j] 最小,很明显m_{k}[i + 1, j] 不是最小的,而 i + 1 ≤ k < d ,也就是说 b 肯定不在[i + 1, d) 所以 b ≥ d)

     ∴           s[i, j] ≤ s[i + 1, j]      同理可得  s[i, j - 1] ≤ s[i, j]

    所以第三重循环的范围就可以从(i, j) 压缩到 (s[i, j - 1], s[i + 1, j])

     

     

    如果讲的有不当之处请多多指出~~转载请注明原地址

    展开全文
  • 如果有兴趣的同学可以用四边形不等式证明一下。   下面是代码,这道题不知道为什么,算斜率的时候用double是错的,long long 却是对的。 #include #include #include #include using namespace std; ...

    正题

          我就以这一题:玩具装箱装玩具来引入我们今天的话题。

          我们先设f[i]表示前i个玩具装的最小费用是多少。

          那么,很明显就有我们枚举一个j,使得j+1到i装在一起,那么就有下面的方程。

          \\f[i]=min(f[j]+(i-j-1+sum[i]-sum[j]-L)^2) \\f[i]=min(f[j]+((sum[i]+i)-(sum[j]+j+L+1)))

          然后我们使a[i]=sum[i]+i,b[i]=sum[i]+i+L+1

          那么就有

          \\f[i]=min(f[j]+(a[i]-b[j])^2) \\f[i]=min(f[j]+a[i]^2-2a[i]b[j]+b[j]^2) \\f[i]=min(f[j]-2a[i]b[j]+b[j]^2)+a[i]^2 \\f[i]=min(-2a[i]b[j]+(f[j]+b[j]^2))+a[i]^2

          上面的推导过程是很明显的。

           接着,我们设k=-2a[i],x=b[j],y=f[j]+b[j]^2

           那么就有

           f[i]=kx+y+a[i]^2

           我们现在已知a[i]^2,k,要找到一组x和y使得f[i]最小。

           我们先把a[i]^2丢掉,就剩下:

           \\f[i]=kx+y \\y=f[i]-kx \\y=-kx+f[i]

           现在就像一条公式了,所以要使f[i]最小,就相当于让一条斜率为-k  (2*a[i]) 的直线,从无穷小往上平移,碰到的第一个点就是要求的x和y。明显这个点肯定在1到i-1的下凸包上,又因为a[i]是递增的,所以决策一定是单调上升的。

          那么证明了决策单调性,可以用常规方法,也可以用维护凸包的方法,维护一下就好了,就像下图,我们每一次选中的点一定是对于这个斜率的“凸”点。如果有兴趣的同学可以用四边形不等式来证明一下。     

           下面是代码,这道题不知道为什么,算斜率的时候用double是错的,long long 却是对的。

    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    using namespace std;
    
    int n,m;
    long long a[50010],b[50010],f[50010];
    struct node{
    	long long x,y;
    }s[50010],now;
    int st=1,ed=1;
    
    long long get_k(node x,node y){
    	return (x.y-y.y)/(x.x-y.x);
    }
    
    int main(){
    	scanf("%d %d",&n,&m);
    	int x,sum=0;
    	a[0]=0;b[0]=m+1;
    	s[st]=(node){b[0],b[0]*b[0]};
    	for(int i=1;i<=n;i++){
    		scanf("%d",&x);
    		sum+=x;
    		a[i]=sum+i;b[i]=sum+i+m+1;
    	}
    	for(int i=1;i<=n;i++){
    		while(st<ed && get_k(s[st],s[st+1])<=2*a[i]) st++;
    		f[i]=-2*a[i]*s[st].x+s[st].y+a[i]*a[i];
    		now=(node){b[i],f[i]+b[i]*b[i]};
    		while(st<ed && get_k(s[ed-1],s[ed])>=get_k(s[ed],now)) ed--;
    		s[++ed]=now;
    	}
    	printf("%lld\n",f[n]);
    }

          有一篇好论文:https://wenku.baidu.com/view/eeb6d3ea19e8b8f67c1cb937.html

          四边形不等式:如果状态x转移到状态y的代价为w[x,y],只要满足

          w[ x , y ] + w[ x+1 , y+1 ]<=w[x+1,y]+w[x,y+1]

          那么这个动态规划问题的决策就是单调的。

          像上面的方程,我们可以把它转化为f[i]=min(f[j]+w[i,j])

          明显w[i,j]=(i-j-1+sum[i]-sum[j]-L)^2是状态i转移到状态j的代价,自己动笔,丰衣足食。

          好的,我们现在研究完了这一题,发现什么,它的x=b[j]=sum[i]+i+L+1是单调上升的,而且斜率-k=2*a[i]=2*(sum[i]+i)=2*sum[i]+2*i也是单调上升的。所以我们可以直接用一个单调队列来维护下凸包,而不用考虑前面的值。

          现在,我们要研究的问题就是(x单调,k不单调)(x不单调,k单调)和(x不单调,k不单调)三个分支问题。

          我现在只会(x不单调,k不单调)的 O(n log2 n) 的解法,其他的也一样可以这样做,但是不知道有没有特殊的 O(n) 解法。

    x不单调,k不单调

           首先我们知道,这种东西会很烦,所以我们就想到了CDQ分治。

           我们先全部按k排序,很明显k是可以根据输入直接得到的,并记录下这个元素原来是在哪里的。

           每次分,我们把(l , r)区间内的,按原来的位置分成左右两堆,下去分治。

           先做左边,每次递归结束后会把这些元素按照x坐标(算出来的),从左到右排序。

           那么左边的序列就是关于x有序的了,我们用左边的构建一个下凸包,然后用右边没有改变过顺序的斜率,去更新每一个节点的答案,然后就完了。

           最后把右边分治一下。递归回来之后,把左边排好序的和右边排好序的做一次类似于归并排序的东西就好了。

           例题有[NOI2007]货币兑换。

    如果多加一维限制,表示x所能取的范围在bound[x]\to x-1之间呢?

           好的,问了一下zhf大佬,是双log的。

           我们构建一棵线段树,以位置为关键字。每个节点维护一个凸包。

           每次我们对一个节点有一个它的斜率,对于bound[x]~x-1这段区间,在线段树上是log个的,把它找出来,它肯定是被完全覆盖的,所以,对于log个区间分别二分就可以了。

           插入一个节点的时候,会更改log个区间,当且仅当这个区间的元素被填满,我们就把它排序构造一个凸包,那么插入的时间也是两个log的。

           这样子就可以完美得完成这个口胡题。

           以上纯属口胡,要做更多的题,才能完善这个恶心有趣的知识体系。

           

    展开全文
  • 首先说明一点,这种方法不是什么题都可以用的,我们要判断DP的情况,看是否能够使用平行四边形不等式来进行优化。一般来说,这种优化还是可以很容易看出来的。 首先两个满足的性质。 四边形不等式 如果有 那么这...

    目录

    概述

    例题

    Post Office

    题目描述

    解题思路

    总结

    Monkey Party

    题目链接

    解题思路

    总结

    评述


    概述

    首先说明一点,这种方法不是什么题都可以用的,我们要判断DP的情况,看是否能够使用平行四边形不等式来进行优化。一般来说,这种优化还是可以很容易看出来的。

    首先两个满足的性质。

    四边形不等式

    如果有w[i][j] + w[i'][j'] <= w[i'][j] + w[i][j'] (i<=i'<=j<=j')

    那么这一个w数组(其实可以说成是函数)满足四边形不等式。看起来比较难理解,四边形不等式是什么东西。我们结合一个图来看,其实这个东西并不难

    在图片中,可以明显地看出(i,j)与(i',j')小于对角线的长度,当然,图形如果不一样的话是可以等于的,这就是比较好理解的四边形不等式。

    决策单调性

    如果有w[i'][j] <= w[i][j'] (i<=i'<=j<=j'),那么可以知道w是具有单调性的。

    当然,上述的判断是比较麻烦的,判断起来十分不方便,于是,我们便可以用朴素的DP算法来打表判断。

    其实还有一种方法,那就是看最优决策。

    最优决策

    这里先列一个状态转移方程,要不然不好说。dp[i][j] = min\left \{ dp[k][j - 1] + w[k + 1 ][j] \right \}

    设s[i][j]为dp[i][j]的k值最优值,即当k取s[i][j]时,我们dp[i][j]的值最小。

    那么问题来了,这东西该如何判断呢。

    那么我们就需要根据题目,尝试比较s[i][j-1],s[i][j],s[i+1][j]等数的大小关系。这样我们就可以确定k的范围。几乎做到了降维的作用,这对于时间的优化可以说是非常大的。

    例题

    Post Office

    题目描述

    There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates. 

    Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum. 

    You are to write a program which, given the positions of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office.

    有一条笔直的公路,公路旁边有村庄。高速公路用一个整数轴表示,每个村庄的位置用一个整数坐标标识。没有两个村庄处于相同的位置。两个位置之间的距离是它们的整数坐标的差的绝对值。
    一些村庄会建邮局,但不一定所有的村庄都会建。一个村庄和它的邮局有相同的位置。在兴建邮政局时,应选择邮政局的位置,使每个村与其最近的邮政局之间的距离总和最少。
    您需要编写一个程序,根据村庄的位置和邮局的数量,计算每个村庄与其最近的邮局之间的所有距离的最小可能和。

    输入

    第一行包含两个整数:第一行是村庄数V, 1 <= V <= 300,第二行是邮局数P, 1 <= P <= 30, P <= V。这些V整数是村庄的位置。对于每个位置X,它保持1 <= X <= 10000。

    输出

    第一行包含一个整数S,它是每个村庄与其最近邮局之间所有距离的总和。

    样例输入

    10 5
    1 2 3 6 7 9 11 22 44 50

    样例输出

    9

    解题思路

    DP思路很好想吧。用dp[i][j]来表示前i个村庄有j个邮局。

    dp[i][j] = min\left \{ dp[k][j - 1] + w[k + 1][i] \right \}

    我们看一看状态转移方程。到i时有j个村庄。到k时有j-1个村庄,那么k就是一个分界点,w我们暂时用来表示花费,其实我们可以知道,从k + 1 到 i中间的这一些村庄是肯定有两种情况的,有些还是要去第j-1个邮局,而有些就要去到第j个邮局,那么我们便要找到这一个分界点,使状态最优了。

    其实根据我们数学的常识,找分界点并不难,若要花费最小,我们最好要保持两边的均衡,于是,取中间的那个村庄(中位数)即可。在这里,估计会有人质疑。我们其实也可以用反证的思想去证明,若中位数不优,那么往左或往右移一定会更小,这个区间两边的村庄个数最多只相差1(两个中位数情况任选其一),我们往左右移是一定不可能最小的。那么分界点弄出来了。但我们还要求这些村庄的距离和。

    这里我们就需要用新的方法进行优化

    我们需要进行预处理,用sum1[i]来表示从1到i的所有村庄到第一个村庄的距离总和,用sum2[i]来表示从i到n的所有村庄到最后一个村庄的距离总和。但这两个数组有什么用呢。其实,有了这两个数组我们就可以求出w了。

    w[i][j] = sum1[j] - sum1[k] - (j - k) * (pos[k] -pos[1] ) + sum2[i] - sum2[k] - (k - i) *(pos[n] - pos[k])

    就是这样求的,看起来很复杂的样子。

    我们结合图来看吧。

    sum1[j] - sum1[k]就是求出了k到j这一段的村庄到1的距离。然而,我们求他们到1的距离是没有啥用的,因此,我们就需要减去k到j这一段村庄中多走的1到k这一段路程。如下图

     同样,sum2也是一样的操作,这个时候,可能有人会尝试一下,可否反着来,即

    w[i][j] = sum1[k] - sum1[i] - (pos[i] - pos[1]) * (k - i) + sum2[k] - sum2[j] -( pos[n] - pos[j]) * (n - j).

    乍一看好像没有问题。。。。实际上是有的,其实放在实际操作中还比较明显。我们由前面的推导可以知道,我们需要求k到j这一部分村庄到k的距离与i到k这一部分村庄到k的距离,如果像这样,不就变成了求k到j这一部分村庄到j的距离加上i到k这一部分村庄到i的距离吗?

    的确,如果反着来,就是这样的操作。

    w求完了,接下来就是做DP了,不过,DP有三个变量,至少也是三重循环,这道题虽然能过,但我们还是想着再优化一下,的确,这道题就需要用平行四边形优化。

    我不管这么多性质,直接看最优决策点之间的关系,用s[i][j]表示令dp[i][j]最优的k。

    那么如果j+1,就是说要多修一个邮局,你那么相应的决策点一定会往后移,你想吧,一段的点,本来平均分配,然而现在多了一个点,肯定给它空间,那么决策点必然后移,

    所以s[i][j] <= s[i][j + 1]

    要让我们的判断的s可以运用到程序中,j我们就不再管了,再来看i,如果i - 1,那么意味着少了一个村庄,那么,原来的决策点可能不平衡了。那么相应地要往多的那边移以此保持平衡态,减少村庄的那边,它是肯定不会移的。

    那么s[i - 1][j] <= s[i][j]。

    所以s[i - 1][j] <= s[i][j] <= s[i][j + 1]

    我们dp的k的范围其实就出来了那么便可以快速地做了

    #include<cstdio> 
    #include<cmath> 
    #include<cstring> 
    #include<iostream> 
    #include<vector> 
    #include<queue> 
    #include<map> 
    #include<cstdlib> 
    #include<algorithm> 
    #define N 1005 
    using namespace std; 
    int n,p,a[N],dp[305][305] , w[305][305] , sum1[305] , sum2[305] , s[305][305];
    int main(){
    	memset(dp,0x3f,sizeof(dp));
    	scanf("%d%d",&n,&p);
    	for (int i = 1 ;i <= n; i ++ ){
    		scanf("%d",&a[i]);
    	}
    	for (int i = 1; i <= n;i ++ ){//求出1到i每个村庄到1的距离
    		sum1[i] = sum1[i - 1] + a[i] - a[1];
    	}
    	for (int i = n ;i >= 1 ;i -- ){//求出n到i每个村庄到n的距离
    		sum2[i] = sum2[i + 1] + a[n] - a[i];
    	}
    	for (int i = 1;i <= n;i ++ ){//预处理出i,j中建一个邮局所需要的花费
    		for (int j = i + 1;j <= n ; j ++ ){
    			if (i == j)
    				w[i][j] = 0;
    			else{
    				int t = (i + j)/2;
    				w[i][j] = sum1[j] - sum1[t] - (j - t) * (a[t] - a[1]) + sum2[i] - sum2[t] - (t - i) * (a[n] - a[t]);
    			}
    		}
    	}
    	dp[0][0] = dp[1][1] = 0;
    	for (int i = 1 ;i <= n ;i ++){
    		for (int j = min(i,p) ;j >= 1; j --){
    			if (s[i][j + 1] == 0)//如果没有值,我们赋一个边界值
    				s[i][j + 1] = i  - 1;
    			if (s[i - 1][j] == 0)
    				s[i - 1][j] = min(i - 1 ,j - 1);
    			if (i == j){
    				dp[i][j] = 0;
    				continue;
    			}
    			for (int k = s[i - 1 ][j] ; k <= s[i][j + 1] ;k ++ ){//枚举k值
    				if (dp[i][j] > dp[k][j - 1] + w[k + 1][i]){
    					dp[i][j] = dp[k][j - 1] + w[k + 1][i];
    					s[i][j] = k;//更新最优决策点
    				}
    			}
    		}
    	}
    	printf("%d",dp[n][p]);
    }
    

    总结

    总的来说,这道题并不是十分轻松或者说是困难,平行四边形的优化在这道题倒不是特别重要,因为数据量小,不优化依旧可以过。但利用前缀和与后缀和求出w数组这也许才是这道题的关键部分,这里还是比较难的,但理解起来却是不难。可以说练这一道题还是有一定的意义。

    Monkey Party

    题目链接

    就是环形的合并石子,我们将原数组复制一份到后面还是跟普通DP一样做。

    解题思路

    首先,列状态转移方程。我们这样看,如果从i,j这一段要合并,最后的花费就一定是i,j的石子个数,先前的花费就要看有哪一个k使得(i,k)(k+1,j)这两组合并最小了。而求(i,k)则。。。是不是很像递归,其实不然,这就是状态转移方程。

    dp[i][j] = min\left \{ dp[i][k] + dp[k + 1][j] + cost(i,j) \right \}

    其中cost很容易求出来,就是两个前缀和相减,sum[j] - sum[i - 1].由于题目说是环形,我们复制数组,再做DP即可。

    此题枚举顺序是一个关键。k是比i大的,我们需要倒着枚举i,k又比j小,我们就要顺着枚举j,k顺着枚举即可。

    最后,以每一个点为开头看看它们dp最小值。即ans = min{dp[i][i + n - 1]}。

    不过,这道题依旧可以用四边形不等式来进行优化。还是那种思路。如果j+1,那么原本i,j的最优决策点s[i][j]是一定会小于等于s[i][j + 1],同样的,s[i - 1][j] <= s[i][j]。

    不过这道题的枚举顺序不同,我们就不能用这种方式来优化,改一下。用s[i][j - 1] <= s[i][j] <= s[i + 1 ][j]即可。

    #include<cstdio> 
    #include<cmath> 
    #include<cstring> 
    #include<iostream> 
    #include<vector> 
    #include<queue> 
    #include<map> 
    #include<cstdlib> 
    #include<algorithm> 
    #define N 1005 
    using namespace std; 
    int n,a[N * 2] , sum[N * 2]  , dp[N * 2][N * 2] ,s[N * 2][N * 2] ;
    long long ans = 1e15;
    int main(){
    	while (scanf("%d",&n)!=EOF){
    		ans = 1e15;
    		memset(dp,0x3f,sizeof(dp));
    		memset(sum,0,sizeof(sum));
    		memset(s,0,sizeof(s));
    		for (int i = 1 ;i <= n ;i ++){
    			scanf ("%d",&a[i]);
    			a[i + n] = a[i];
    		}
    		for (int i = 1;i <= n * 2;i ++){
    			sum[i] = sum[i - 1] + a[i];
    			s[i][i] = i;
    		}
    		for (int i = 0;i <= 2 * n;i ++)
    			dp[i][i] = 0;
    		for (int i = n * 2;i >= 1 ;i -- ){
    			for (int j = i + 1;j <= n * 2  ;j ++ ){
    				if (!s[i][j - 1])
    					s[i][j - 1] = i;
    				if (!s[i + 1][j])
    					s[i + 1][j] = j - 1;
    				if (i == j)
    					continue;
    				for (int k = s[i][j - 1] ;k <= s[i + 1][j] ;k ++ ){
    					if (dp[i][j] > dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]){
    						dp[i][j] = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1] ;
    						s[i][j] = k;
    					}
    				}
    			}
    		}
    		for (int i = 1 ;i <= n; i ++){
    			ans = ans < dp[i][i + n - 1]?ans:dp[i][i + n - 1];
    		}
    		printf("%lld\n",ans);
    	}
    }

    总结

    这道题很坑。。。。主要我没仔细读题,他那个描述是英文的,我翻译大概看了一遍就没管了,上课讲了题目的,我以为理解了题目,最后发现这道题多组数据,害我错了很多次,这道题dp式子可以说是很单纯的,很少有两个都表示编号。环的处理方法不止这一种,据说还有一种方式叫破环为链,一次逛本校大佬ljh的博客看到过,在这里给一个链接。不是这道题的。感觉方式方法差不多。。。

    评述

    平行四边形优化我认为还是比较基础的DP优化,因为他的性质并不难找。仅仅需要假设然后想象一番就可以确定题目是否可以用平行四边形的优化了,计算量看来是不大的,也许是我现在接触到的题目比较基础的样子。但这一种处理的方式是比较巧妙的,因为平时做DP,哪里想到利用其中变量的关系来进行优化呢?因此,这一种优化方法我认为是需要熟记与运用的。

    展开全文
  • 这大概是跟斜率优化一样神的东西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.使用场合: 优化转移: 1.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)\}dp(i,j)=min{dp(i,k)+dp(k,j)+w(i,j)} 2.dp(i,j)=min{dp(i−1,k−1)+w(k,j)}dp(i,j)=min\{...
  • 四边形不等式优化讲解(详解)

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

    2019-10-06 17:10:39
    四边形不等式优化 填坑 简介 在动态规划问题中 我们常遇到这样一类问题,它的dp方程长这样 \[f[i][j] = min \{ f[i][k] + f[k + 1][j]+cost[i][j] \} \] 这样我们的复杂度一般是\(O(n^3)\)的 设\(a < b <= c &...
  • 四边形不等式

    2012-06-30 20:54:00
    利用四边形不等式来进行优化的讲解及主要代码!
  • 四边形不等式 定义:设\(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\)满足...
  • 动态规划专题小结:四边形不等式优化

    万次阅读 多人点赞 2015-05-15 22:36:54
    今天第一次学习四边形不等式优化dp,感觉优化效果十分给力,不过数学味道比较浓重,证明比较复杂。因此这里删繁就简,给出关于四边形不等式优化必须要明白的地方,以后直接套用条件即可。 四边形不等式优化条件 在...
  • 四边形不等式应用

    2020-01-10 13:18:44
    动态规划加速原理之四边形不等式 动态规划的四边形不等式优化是对特定形式的状态转移方程进行优化的一种方法,该方法可以将复杂度由 O(n3)O(n^3)O(n3) 优化到 O(n2)O(n^2)O(n2)。 设我们有状态转移方程 m(i,j)={min{...
  • 看了那么久的四边形不等式优化的原理,今天终于要写一篇关于它的证明了。 在平时的做题中,我们会遇到这样的区间dp问题 它的状态转移方程形式一般为dp[i][j]=min(dp[i][k]+dp[k+1][j]+cost[i][j]);(或者是max...
  • 题意:给定一些点(xi,yi)(xj,yj)满足:i<j,xi<xj,yi>yj。用下面的连起来,使得所有边的长度最小? 题解:直接给出吧 f[i][j]=min(f[i][k]+f[k+1]...证明一下,搞一搞,四边形性质就出来了,模板题吧。 ...
  • 另外,相当多四边形不等式的递推式子还是需要证明的,因此,这篇论文有时间还是需要好好研究。  顺便提到一件事,最优矩阵链乘问题(MCM)的dp方法,是没有办法采用四边形不等式优化的,原因是递推式的权值项不仅和i...
  • 四边形不等式优化dp专题
  • 壹:证明cost为凸(满足四边形不等式) 贰:证明dp为凸(满足四边形不等式) 叁:证明决策单调(以找min值为例) ~PART THREE 合并石子问题 第一步(壹)证明cost为凸 第二步(贰)证明dp为凸 第三步(叁)...
  • 形如本题的状态转移方程都可以用四边形不等式优化,这里不再证明。(实在不会证可以拿优化过的和裸dp的对拍啊,四边形不等式不难写) 这里介绍一下边界: 只有一堆石子时, f ( i , i ) = 0 f(i,i)=0 , f ( i ,...
  • 四边形不等式 设函数\(w(x,y)\)是定义在\(Z\)上的函数,若对于任意\(a,b,c,d \in Z\),其中\(a\leq b \leq c \leq d\), 都有\(w(a,d)+w(b,c)\ge w(a,c)+w(b,d)\),则称函数\(w\)满足四边形不等式 推论: 设函数\(w...
  • 平行四边形不等式是个啥? 1.题目引入:猴子派对 输入 输出 样例输入 样例输出 2.找出状态转移方程式 3.探索此状态转移方程式的性质 4.细节处理 1.环 2.循环顺序问题 5.更清晰的思维 6.代码 7.变式 1....
  • 四边形不等式小结

    2019-06-06 13:02:00
    目录 四变形不等式 定义 性质 四边形不等式判定定理 一维线性递推优化 优化式 性质 一维递推决策递增定理 实现 二维区间递推优化...
  • 四边形不等式优化dp

    2018-04-19 11:43:52
    我们考虑一个简单的问题:如何验证一个矩阵是否满足四边形不等式? 显然有 O ( n 2 m 2 ) O ( n 2 m 2 ) O(n^2m^2) 的算法,但事实上我们可以依靠下面的性质在 O ( n m ) O ( n m ) O(nm) 的复杂度内判断: ∀ ...
  • 形式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]
  • 四边形不等式的核心在于缩小最优转移的范围 题目描述 传送门 解析 这道题说是不等式,但其实也可以感性理解 (其实就是不想证明) 定义pl[i][k]: i到n的村庄建造k座邮局时,第一座管辖的范围是i-pl[i][k] (也就是...

空空如也

空空如也

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

四边形不等式证明