题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3506
题目大意:就是环形的一堆石子进行合并,合并代价为合并成一堆石子的总重量。
普通的石子合并,这里是不能用的。O(n^3)复杂度会T。必须进行优化,优化方法:四边形不等式优化。
转:https://www.cnblogs.com/hadilo/p/5800306.html
在动态规划中,经常遇到形如下式的状态转移方程:
dp(i,j)=min{dp(i,k-1),dp(k,j)}+s(i,j)(i≤k≤j)(min也可以改为max)
上述的m(i,j)表示区间[i,j]上的某个最优值。s(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的和)
下面给出两个定理:
1、如果上述的 w 函数同时满足区间包含单调性和四边形不等式性质,那么函数 m 也满足四边形不等式性质
我们再定义 W(i,j) 表示 dp(i,j) 取得最优值时对应的下标(即 i≤k≤j 时,k 处的 s 值最大,则 W(i,j)=k)。
此时有如下定理:
2、假如 dp(i,j) 满足四边形不等式,那么 W(i,j) 单调,即 W(i,j)≤W(i,j+1)≤W(i+1,j+1)。
好了,有了上述的两个定理后,我们发现如果w函数满足区间包含单调性和四边形不等式性质,
那么有 dp(i,j-1)≤dp(i,j)≤dp(i+1,j) 。
即原来的状态转移方程可以改写为下式:
dp(i,j)=min{dp(i,k-1),dp(k,j)}+s(i,j)(W(i,j-1)≤k≤W(i+1,j))(min也可以改为max)
由于这个状态转移方程枚举的是区间长度 L=j-i,而 W(i,j-1) 和 W(i+1,j) 的长度为 L-1,是之前已经计算过的,可以直接调用。
不仅如此,区间的长度最多有n个,对于固定的长度 L,不同的状态也有 n 个,
故时间复杂度为 O(N^2),而原来的时间复杂度为 O(N^3),实现了优化!
今后只需要根据方程的形式以及 w 函数是否满足两条性质即可考虑使用四边形不等式来优化了。
思路:相当于之前的直线石子合并 将前n-1堆石子复制到n+1到2n-1,变成一个2n-1长的直线石子合并问题
中间我进行了四边形不等式的优化,即加入了决策
W[ i ][ j ]表示在区间[ i, j ] 取得最大值时的k。 w[i][j-1]<=w[i][j]<=w[i+1][j] 这样减少了k的枚举。复杂度变成O(n^2)
#include<bits/stdc++.h>
using namespace std;
int a[2005];
int s[2005];
int dp[2005][2005];
int wz[2005][2005];
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
memset(s, 0, sizeof(s));
memset(dp, 0, sizeof(dp));
for(int i=1;i<=n*2-1;i++)
{
wz[i][i]=i;//k的初始化
if(i<=n)
{
s[i]=s[i-1]+a[i];
}
else
{
s[i]=s[i-1]+a[i%n];
}
}
for(int Len=2;Len<=n;Len++)
{
for(int L=1;L<=n*2-Len;L++)//长度发生改变
{
int R=L+Len-1;
dp[L][R]=100000000;
for(int k=wz[L][R-1];k<=wz[L+1][R];k++)
{
if(dp[L][R]>dp[L][k]+dp[k+1][R]+s[R]-s[L-1])//四边形优化
{
dp[L][R]=dp[L][k]+dp[k+1][R]+s[R]-s[L-1];
wz[L][R]=k;
}
}
}
}
int Min=100000000;
for(int i=1;i<=n;i++)//找区间长度为n
{
Min=min(dp[i][i+n-1], Min);
}
cout<<Min<<endl;
}
return 0;
}