dp的平行四边形优化

先来看一道题目：

有 \(n\) 堆石子排成一行，第 \(i\) 堆有 \(a_i\) 个石子每次选择相邻的两堆石子，将其合并为一堆，记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数，求当所有石子合并为一堆时，最小的总得分。

区间DP模板题。设 \(dp(i,j)\) 为区间 \([i,j]\) 的最小得分，则状态转移方程为：

\[dp(i,j) = \min_{k=i}^{j-1}\{dp(i,k)+dp(k+1,j)+\sum_{s=i}^j a_s\}
\]

code:

#include<bits/stdc++.h>

using namespace std;

const int inf=1<<30;

int dp[1005][1005],a[1005],sum[1005]; //sum[]数组为a[]数组的前缀和，这样就能快速求出∑a_s(i<=s<=j)。

int main()

{

	int n,i,j,k,s;

	scanf("%d",&n);

	for(i=1;i<=n;i++) dp[i][i]=0;

	sum[0]=0;

	for(i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

		sum[i]=sum[i-1]+a[i];

	}

	for(k=1;k<n;k++)

	{

		for(i=1;i<=n-k;i++)

		{

			j=i+k;

			dp[i][j]=inf;

			for(s=i;s<j;s++)

				dp[i][j]=min(dp[i][j],dp[i][s]+dp[s+1][j]+sum[j]-sum[i-1]);

		}

	}

	printf("%d\n",dp[1][n]);

	return 0;

}

容易看出，上面的代码时间复杂度为 \(O(n^3)\)，数据一旦大一点，就会导致 TLE。

怎么办呢？我们来看代码的循环部分：

for(k=1;k<n;k++)

{

	for(i=1;i<=n-k;i++)

	{

		j=i+k;

		dp[i][j]=inf;

		for(s=i;s<j;s++)

			dp[i][j]=min(dp[i][j],dp[i][s]+dp[s+1][j]+sum[j]-sum[i-1]);

	}

}

前两层循环枚举距离和起点，无法优化，但是第三层循环寻找断点是可以优化的。怎么做呢？

可以再开一个 \(s\) 数组来记录每个区间的最优断点，然后变量 \(k\) （寻找断点）每次只从 \(s(i,j-1)\) 循环到 \(s(i+1,j)\)，这样时间复杂度可以从 \(O(n^3)\) 降到近似 \(O(n^2)\)。

如何证明这样的循环来找断点是对的呢？

见下：（Edited by charliezhi2007）

DP的平行四边形不等式证明，m[i][j]即为dp[i][j]，s[i][j]表示i~j的最优化断点。

设a , b , c , d（a<=b<=c<=d）    //结论是两边之和大于第三边（四边形）

m(a,c) + m(b,d) <= m(a,d) + m(b,c)    //四边形对边相等

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

s[ i ][ j ]<=s[i+1][ j ]思考

d=s[ i ][ j ] ,i < i + 1 <= k < d      k<-[ i , j ]        //设d为断点位置，假设k小于d，k为i，j中任意断点

mk(i,j) = m(i,k) + m(k + 1,j) + sum(i,j) //表示以k为断点i，j合并的代价   sum是i到j所有值得和

md(i,j) = m(i,d) + m(d + 1,j) + sum(i,j)    //表示以d为断点i，j合并的代价（代价最小）

mk(i,j) >= md(i,j) > 0           //d为断点将i，j合并的代价最小因为d是最优断点

=> mk(i,j) - md(i,j) > 0                            

(mk(i + 1,j) - md(i + 1,j)) - (mk(i,j) - md(i,j))         //判断k>d 或 d>k因为上面假设k<d要证明

=(mk(i + 1,j) + md(i,j)) - (md(i + 1,j) + mk(i,j))     //将系数为负数的项，系数为正数的项放在一起

=    (m(i + 1,k) + m(k + 1,j) + m(i,d) + m(d + 1,j) + sum(i,j) + sum(i + 1,j))

    - (m(i + 1,d) + m(k + 1,j) + m(i,k) + m(k + 1,j)+ sum(i,j) + sum(i + 1,j))      //将式子展开

=>将减号两边的m(k + 1,j) 和 m(d + 1,j) 和 sum(i,j) 和 sum(i + 1,j)相互消元

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

=> i<i + 1<k <d       =       a <b <c <d            //两式变量相等

=>(m(i + 1,k) + m(i,d)) - (m(i + 1,d) + m(i,k))     =     (m(b,c) + m(a,d)) - (m(b,d) + m(a,c))     >0      //因ad+bc>=ac+bd所以该式大于0

=>(mk(i + 1,j) - md(i + 1,j)) - (mk(i,j) - md(i,j)) >0            //则这个也大于0

因d<=b    则b=s[i + 1][ j ]

下面求s[ i ][j-1]的思路于上面一致，则最终得出k∈[s[ i ][j-1] , s[i-1][ j ]]。

通过上述推论，可得出 \(s(i,j-1)\leq s(i,j)\leq s(i+1,j)\)，再经过一波分析，可得出 \(s(i+1,j)-s(i,j-1)\) 小到几乎可以忽略不计，所以上述程序的复杂度降到了 \(O(n^2)\)。

献上丑陋AC代码：

#include<bits/stdc++.h>

using namespace std;

const int inf=1<<30;

int dp[1005][1005],a[1005],sum[1005],s[1005][1005];

int main()

{

	int n,i,j,k,ss;

	scanf("%d",&n);

	for(i=1;i<=n;i++)

	{

		dp[i][i]=0;

		s[i][i]=i;

	}

	sum[0]=0;

	for(i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

		sum[i]=sum[i-1]+a[i];

	}

	for(k=1;k<n;k++)

	{

		for(i=1;i<=n-k;i++)

		{

			j=i+k;

			dp[i][j]=inf;

			for(ss=s[i][j-1];ss<=s[i+1][j];ss++)

			{

				if(dp[i][ss]+dp[ss+1][j]+sum[j]-sum[i-1]<dp[i][j])

				{

					dp[i][j]=dp[i][ss]+dp[ss+1][j]+sum[j]-sum[i-1];

					s[i][j]=ss;

				}

			}

		}

	}

	printf("%d\n",dp[1][n]);

	return 0;

}

巴特西

dp的平行四边形优化

最新文章

热门文章