四边形不等式优化dp专题
区间类dp的优化
几点性质
性质1，若函数
w
(
l
,
r
)
w(l,r)
w(l,r)满足四边形不等式，则状态
f
(
l
,
r
)
f(l,r)
f(l,r)也满足四边形不等式。
性质2，若状态f满足四边形不等式，记
m
l
,
r
m_{l,r}
ml,r表示状态
f
l
,
r
f_{l,r}
fl,r的最优决策点，那么必有
m
l
,
r
−
1
≤
m
l
,
r
≤
m
l
+
1
,
r
m_{l,r-1}\leq m_{l,r}\leq m_{l+1,r}
ml,r−1≤ml,r≤ml+1,r
以上两性质的证明参见OI-wiki
核心代码
for (int len
= 2; len
<= n
; ++len
)
for (int l
= 1, r
= len
; r
<= n
; ++l
, ++r
) {
f
[l
][r
] = INF
;
for (int k
= m
[l
][r
- 1]; k
<= m
[l
+ 1][r
]; ++k
)
if (f
[l
][r
] > f
[l
][k
] + f
[k
+ 1][r
] + w(l
, r
)) {
f
[l
][r
] = f
[l
][k
] + f
[k
+ 1][r
] + w(l
, r
);
m
[l
][r
] = k
;
}
}
T1 二叉搜索树
解析
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示将
i
−
j
i-j
i−j中的所有节点建成一颗二叉搜索树，所需要付出的代价的最小值，因此可以用区间dp解决该题。
f
[
i
]
[
j
]
=
m
i
n
(
f
[
i
]
[
k
−
1
]
+
f
[
k
+
1
]
[
j
]
+
x
[
i
.
.
j
]
)
f[i][j]=min{(f[i][k-1]+f[k+1][j]}+x[i..j])
f[i][j]=min(f[i][k−1]+f[k+1][j]+x[i..j])表示我们当前要以k为根节点，合并
i
.
.
.
k
−
1
,
k
+
1...
j
i...k-1,k+1...j
i...k−1,k+1...j的节点为一棵二叉搜索树，因为合并后，每个节点会向下一层，因此我们要多付出的代价为
x
i
+
.
.
.
+
x
j
x_i+...+x_j
xi+...+xj,可以用前缀和来维护，即
s
u
m
j
−
s
u
m
i
−
1
sum_j-sum_{i-1}
sumj−sumi−1;
但这样的时间复杂度为
O
(
n
3
）
O(n^3）
O(n3）,因此我们要考虑优化。
因为不会斜率优化dp ，因此考虑四边形不等式优化dp，然而我不会证明该题对于四边形不等式成立，因此可以通过打表来寻找规律，最后发现它具有决策单调性，因此时间复杂度优化至
O
（
n
2
）
O（n^2）
O（n2）
题解
#include<bits/stdc++.h>
#define INF 1e18
using namespace std
;
long long f
[5011][5011],sum
[5100],n
;
int g
[5011][5011],v
;
inline long long read()
{
long long f
=1,re
=0;
char ch
;
for(ch
=getchar();(ch
<'0'||ch
>'9')&&ch
!='-';ch
=getchar());
if(ch
=='-')
{
f
=-1;
ch
=getchar();
}
for(;(ch
>='0'&&ch
<='9');ch
=getchar())
re
=(re
<<3)+(re
<<1)+ch
-'0';
return re
*f
;
}
signed main()
{
long long x
;
n
=read();
for(int i
=1;i
<=n
;i
++)
{
x
=read();
sum
[i
]=sum
[i
-1]+x
;
f
[i
][i
]=x
;
g
[i
][i
]=i
;
}
for(int i
=1;i
<n
;i
++)
for(int j
=1;(v
=j
+i
)<=n
;j
++)
{
f
[j
][v
]=INF
;
for(int k
=g
[j
][v
-1];k
<=g
[j
+1][v
];k
++)
if(f
[j
][v
]>f
[j
][k
-1]+f
[k
+1][v
])
{
f
[j
][v
]=f
[j
][k
-1]+f
[k
+1][v
];
g
[j
][v
]=k
;
}
f
[j
][v
]+=(sum
[v
]-sum
[j
-1]);
}
printf("%lld",f
[1][n
]);
return 0;
}
T2 玩具装箱
解析
首先可以容易地得到dp方程为
f
[
i
]
=
m
i
n
(
f
[
j
]
+
(
s
u
m
[
i
]
−
s
u
m
[
j
]
+
i
−
j
−
1
−
l
)
2
)
(
j
∈
[
1
,
i
)
)
f[i]=min(f[j]+(sum[i]-sum[j]+i-j-1-l)^2)(j\in[1,i))
f[i]=min(f[j]+(sum[i]−sum[j]+i−j−1−l)2)(j∈[1,i))
f
[
i
]
f[i]
f[i]表示前i个玩具用容器装好后的最小代价；
但很明显，这样会超时，因此考虑四边形不等式优化dp，从而降低时间复杂度，该题可以较容易的证得四边形不等式成立，从而证出决策单调性；
证明过程如下： （
c
[
i
]
c[i]
c[i]表示单个玩具的长度）
题解
#include<bits/stdc++.h>
#define INF 1e18
using namespace std
;
long long n
,l
,f
[50001],sum
[50001],g
[50001];
long long read()
{
int f
=1;
long long re
=0;
char ch
;
for(ch
=getchar();(ch
<'0'||ch
>'9')&&ch
!='-';ch
=getchar());
if(ch
=='-')
{
f
=-1;
ch
=getchar();
}
for(;ch
>='0'&&ch
<='9';ch
=getchar())
re
=(re
<<3)+(re
<<1)+ch
-'0';
return re
*f
;
}
signed main()
{
int x
;
n
=read();
l
=read();
for(int i
=1;i
<=n
;i
++)
{
x
=read();
sum
[i
]=sum
[i
-1]+x
;
}
for(int i
=1;i
<=n
;i
++)
{
f
[i
]=INF
;
for(int j
=g
[i
-1];j
<i
;j
++)
{
long long k
=(sum
[i
]-sum
[j
]+i
-j
-1-l
)*(sum
[i
]-sum
[j
]+i
-j
-1-l
);
if(f
[i
]>f
[j
]+k
)
{
f
[i
]=f
[j
]+k
;
g
[i
]=j
;
}
}
}
printf("%lld",f
[n
]);
return 0;
}
题外话
该题可以用斜率优化dp，我不会qwq 先放篇斜率优化dp题解 传送门
T3 邮局
解析
首先我们需要明确一点，邮局是建立在村庄里的（fhm觉得不用放在村庄, 我觉得他理解题意理解得非常到位 ），然后根据人类的智慧就可以得出结论 ，在
[
l
,
r
]
[l,r]
[l,r]的区间中，将邮局放在中间位置的村庄最优。 咳咳 ，其实可以证明，如下图： 因此我们先预处理处任意区间内，放一个邮局的最小代价，然后我们就可以得出dp方程：
f
[
i
]
[
j
]
=
m
i
n
(
f
[
k
]
[
j
−
1
]
+
d
[
k
+
1
]
[
i
]
)
)
(
k
∈
[
1
,
i
)
f[i][j]=min(f[k][j-1]+d[k+1][i]))(k\in[1,i)
f[i][j]=min(f[k][j−1]+d[k+1][i]))(k∈[1,i) (
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示前i个村庄，已经放了j个邮局) 然后显然会超时，所以考虑四边形不等式优化do，证明其决策单调性 证明过程如下： 然而并没有，因为我不会证明 但是可以通过打表来找规律
题解
#include<bits/stdc++.h>
#define INF 1e8
using namespace std
;
int d
[3003][3003],sum
[3003],f
[3004][3004];
int g
[3004][3004],n
,p
,a
[3005];
int main()
{
scanf("%d%d",&n
,&p
);
for(int i
=1;i
<=n
;i
++)
{
scanf("%d",&a
[i
]);
sum
[i
]=sum
[i
-1]+a
[i
];
}
for(int l
=1;l
<=n
;l
++)
for(int r
=l
;r
<=n
;r
++)
{
long long mid
=(l
+r
)>>1;
d
[l
][r
]=(mid
-l
)*a
[mid
]-sum
[mid
-1]+sum
[l
-1];
d
[l
][r
]+=(sum
[r
]-sum
[mid
]-(r
-mid
)*a
[mid
]);
}
memset(f
,127,sizeof(f
));
for(int i
=1;i
<=n
;i
++)
f
[i
][1]=d
[1][i
];
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=p
;j
++)
for(int k
=g
[i
][j
-1];k
<=i
;k
++)
{
if(f
[i
][j
]>f
[k
][j
-1]+d
[k
+1][i
])
{
f
[i
][j
]=f
[k
][j
-1]+d
[k
+1][i
];
g
[i
][j
]=k
;
}
}
printf("%d",f
[n
][p
]);
return 0;
}
