- 动态规划加速原理
- 石子问题
- 输入格式
- 输出格式
- 数据范围
- O ( n 3 ) O(n^3) O(n3)时间算法
- 四边形不等式
- 1）情形1：
i
<
i
′
=
j
<
j
′
i
- (1) 情形1.1： k ⩽ j kleqslant j k⩽j
- (2) 情形1.2： k > j k>j k>j
- 2) 情形2： i < i ′ < j < j ′ i
- (1) 情形2.1： z ⩽ y zleqslant y z⩽y
- (2) 情形2.2： z > y z>y z>y
- 1）情形1：
i
<
i
′
=
j
<
j
′
i
- 加速算法
- 测试
有 N N N 堆石子排成一排，其编号为 1 , 2 , 3 , … , N 1,2,3,…,N 1,2,3,…,N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N N N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1，2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4 + 9 + 11 = 24 4+9+11=24 4+9+11=24；
如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4 + 7 + 11 = 22 4+7+11=22 4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式第一行一个数 N N N 表示石子的堆数 N N N。
第二行 N N N 个数，表示每堆石子的质量(均不超过 1000)。
输出格式输出一个整数，表示最小代价。
数据范围1 ≤ N ≤ 300 1≤N≤300 1≤N≤300
石子问题的动态规划递归式使下面更一般的递归计算式的特殊情形。
设
w
(
i
,
j
)
∈
R
,
1
⩽
i
<
j
⩽
n
w(i,j)in R,1leqslant i < j leqslant n
w(i,j)∈R,1⩽i 在上述计算
m
(
i
,
j
)
m(i,j)
m(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
)
,
i
⩽
i
′
<
j
⩽
j
′
w(i^{'},j)leqslant w(i^{'},j),ileqslant i^{'} 对于满足四边形不等式的单调函数
w
w
w，可推知由递归式定义的函数
m
(
i
,
j
)
m(i,j)
m(i,j)也满足四边形不等式，即 证明思路：假设
w
(
i
,
j
)
w(i,j)
w(i,j)满足四边形不等式且关于区间包含关系单调，先证明
l
⩽
1
lleqslant 1
l⩽1时成立，再假设
l
<
j
′
−
i
l 假设
w
(
i
,
j
)
w(i,j)
w(i,j)满足四边形不等式且关于区间包含关系单调。当
i
=
i
′
i=i^{'}
i=i′或
j
=
j
′
j=j^{'}
j=j′时，不等式显然成立。由此可知，当
l
⩽
1
lleqslant 1
l⩽1时，函数
m
m
m满足四边形不等式。 假设
l
<
j
′
−
i
l 此时有
m
(
i
,
j
′
)
=
w
(
i
,
j
′
)
+
m
(
i
,
k
−
1
)
+
m
(
k
,
j
′
)
m(i,j^{'})=w(i,j^{'})+m(i,k-1)+m(k,j^{'})
m(i,j′)=w(i,j′)+m(i,k−1)+m(k,j′)。因此有 同(1)也有
m
(
i
,
j
′
)
=
w
(
i
,
j
′
)
+
m
(
i
,
k
−
1
)
+
m
(
k
,
j
′
)
m(i,j^{'})=w(i,j^{'})+m(i,k-1)+m(k,j^{'})
m(i,j′)=w(i,j′)+m(i,k−1)+m(k,j′)。同理也有 由定义有 因为
i
′
⩽
y
⩽
z
i^{'}leqslant y leqslant z
i′⩽y⩽z且
z
<
j
′
z 定义
s
(
i
,
j
)
=
m
a
x
{
k
∣
m
(
i
,
j
)
=
m
(
i
,
k
−
1
)
+
m
(
k
,
j
)
+
w
(
i
,
j
)
}
s(i,j)=max{k|m(i,j)=m(i,k-1)+m(k,j)+w(i,j)}
s(i,j)=max{k∣m(i,j)=m(i,k−1)+m(k,j)+w(i,j)}，由
m
(
i
,
j
)
m(i,j)
m(i,j)的四边形不等式可以推出
s
(
i
,
j
)
s(i,j)
s(i,j)的单调性，即 当
i
<
j
i 又因为
m
k
′
(
i
,
j
)
⩽
m
k
(
i
,
j
)
m_{k^{'}}(i,j)leqslant m_k(i,j)
mk′(i,j)⩽mk(i,j)，可得
m
k
′
(
i
.
j
+
1
)
⩽
m
k
(
i
,
j
+
1
)
m_{k^{'}}(i.j+1)leqslant m_k(i,j+1)
mk′(i.j+1)⩽mk(i,j+1)，因此，
(
i
,
j
+
1
)
(i,j+1)
(i,j+1)的最优断开点必在
k
′
k^{'}
k′的右端，即
s
(
i
,
j
)
⩽
s
(
i
,
j
+
1
)
s(i,j)leqslant s(i,j+1)
s(i,j)⩽s(i,j+1) 。 同理，设
k
′
k^{'}
k′为
(
i
+
1
,
j
+
1
)
(i+1,j+1)
(i+1,j+1)的最优断开点，则对所有
i
+
1
<
k
′
⩽
k
⩽
j
+
1
i+1
m
(
i
,
k
)
m(i,k)
m(i,k)满足四边形不等式，有 又因为
m
k
′
(
i
+
1
,
j
+
1
)
⩽
m
k
(
i
+
1
,
j
+
1
)
m_{k^{'}}(i+1,j+1)leqslant m_k(i+1,j+1)
mk′(i+1,j+1)⩽mk(i+1,j+1)，可得
m
k
′
(
i
,
j
+
1
)
⩽
m
k
(
i
,
j
+
1
)
m_{k^{'}}(i,j+1)leqslant m_k(i,j+1)
mk′(i,j+1)⩽mk(i,j+1)，因此，
(
i
,
j
+
1
)
(i,j+1)
(i,j+1)的最优断开点必在
k
′
k^{'}
k′左端，即
s
(
i
,
j
+
1
)
⩽
s
(
i
+
1
,
j
+
1
)
s(i,j+1)leqslant s(i+1,j+1)
s(i,j+1)⩽s(i+1,j+1)。 综上，当
w
w
w是满足四边形不等式的单调函数时，
s
(
i
,
j
)
s(i,j)
s(i,j)单调，从而有 改进后算法所需的计算时间为： 对于数据： 加速前运行结果：#include
w
(
i
,
j
)
+
w
(
i
′
,
j
′
)
⩽
w
(
i
′
,
j
)
+
w
(
i
,
j
′
)
,
i
⩽
i
′
<
j
⩽
j
′
w(i,j)+w(i^{'},j^{'})leqslant w(i^{'},j) + w(i,j^{'}),qquad space ileqslant i^{'} < j leqslant j^{'}
w(i,j)+w(i′,j′)⩽w(i′,j)+w(i,j′), i⩽i′
m
(
i
,
j
)
+
m
(
i
′
,
j
′
)
⩽
m
(
i
′
,
j
)
+
m
(
i
,
j
′
)
,
i
⩽
i
′
<
j
⩽
j
′
m(i,j)+m(i^{'},j^{'}) leqslant m(i^{'},j)+m(i,j^{'}),qquad space ileqslant i^{'} < j leqslant j^{'}
m(i,j)+m(i′,j′)⩽m(i′,j)+m(i,j′), i⩽i′
m
(
i
,
j
)
+
m
(
j
,
j
′
)
⩽
m
(
i
,
j
′
)
m(i,j)+m(j,j^{'})leqslant m(i,j^{'})
m(i,j)+m(j,j′)⩽m(i,j′)
设
k
=
m
a
x
{
t
∣
m
(
i
,
j
′
)
=
m
(
i
,
t
−
1
)
+
m
(
t
,
j
′
)
+
w
(
i
,
j
′
)
}
k=max{t|m(i,j^{'})=m(i,t-1)+m(t,j^{'})+w(i,j^{'})}
k=max{t∣m(i,j′)=m(i,t−1)+m(t,j′)+w(i,j′)}，即
k
k
k为所有取得最小值的分割点中最大的一个
m
(
i
,
j
)
+
m
(
j
,
j
′
)
⩽
w
(
i
,
j
)
+
m
(
i
,
k
−
1
)
+
m
(
k
,
j
)
+
m
(
j
,
j
′
)
⩽
w
(
i
,
j
′
)
+
m
(
i
,
k
−
1
)
+
m
(
k
,
j
)
+
m
(
j
,
j
′
)
⩽
w
(
i
,
j
′
)
+
m
(
i
,
k
−
1
)
+
m
(
k
,
j
′
)
=
m
(
i
,
j
′
)
m(i,j)+m(j,j^{'})leqslant w(i,j)+m(i,k-1)+m(k,j)+m(j,j^{'})\ leqslant w(i,j^{'})+m(i,k-1)+m(k,j)+m(j,j^{'})\ leqslant w(i,j^{'})+m(i,k-1)+m(k,j^{'})\ =m(i,j^{'})
m(i,j)+m(j,j′)⩽w(i,j)+m(i,k−1)+m(k,j)+m(j,j′)⩽w(i,j′)+m(i,k−1)+m(k,j)+m(j,j′)⩽w(i,j′)+m(i,k−1)+m(k,j′)=m(i,j′)
第一次放缩是因为
k
k
k是
(
i
,
j
′
)
(i,j^{'})
(i,j′)取得最小值的分割点，但不是
(
i
,
j
)
(i,j)
(i,j)取得最小值的分割点，因此是放大；第二次放缩是因为
w
w
w的区间包含关系单调；第三次放缩由归纳假设，即
l
<
j
′
−
i
l
m
(
i
,
j
)
+
m
(
j
,
j
′
)
⩽
m
(
i
,
j
)
+
w
(
j
,
j
′
)
+
m
(
j
,
k
−
1
)
+
m
(
k
,
j
′
)
⩽
m
(
i
,
j
)
+
w
(
i
,
j
′
)
+
m
(
j
,
k
−
1
)
+
m
(
k
,
j
′
)
⩽
w
(
i
,
j
′
)
+
m
(
i
,
k
−
1
)
+
m
(
k
,
j
′
)
=
m
(
i
,
j
′
)
m(i,j)+m(j,j^{'})leqslant m(i,j)+w(j,j^{'})+m(j,k-1)+m(k,j^{'})\ leqslant m(i,j)+w(i,j^{'})+m(j,k-1)+m(k,j^{'})\ leqslant w(i,j^{'})+m(i,k-1)+m(k,j^{'})\ =m(i,j^{'})
m(i,j)+m(j,j′)⩽m(i,j)+w(j,j′)+m(j,k−1)+m(k,j′)⩽m(i,j)+w(i,j′)+m(j,k−1)+m(k,j′)⩽w(i,j′)+m(i,k−1)+m(k,j′)=m(i,j′)
第一次放缩是因为
k
k
k是
(
i
,
j
′
)
(i,j^{'})
(i,j′)取得最小值的分割点，但不是
(
j
,
j
′
)
(j,j^{'})
(j,j′)取得最小值的分割点，因此是放大；第二次放缩是因为
w
w
w的区间包含关系单调；第三次放缩由归纳假设，即
l
<
j
′
−
i
l
y
=
m
a
x
{
t
∣
m
(
i
′
,
j
)
=
m
(
i
′
,
t
−
1
)
+
m
(
t
,
j
)
+
w
(
i
′
,
j
)
}
z
=
m
a
x
{
t
∣
m
(
i
,
j
′
)
=
m
(
i
,
t
−
1
)
+
m
(
t
,
j
′
)
+
w
(
i
,
j
′
)
}
y=max{t|m(i^{'},j)=m(i^{'},t-1)+m(t,j)+w(i^{'},j)}\ z=max{t|m(i,j^{'})=m(i,t-1)+m(t,j^{'})+w(i,j^{'})}
y=max{t∣m(i′,j)=m(i′,t−1)+m(t,j)+w(i′,j)}z=max{t∣m(i,j′)=m(i,t−1)+m(t,j′)+w(i,j′)}
即
y
,
x
y,x
y,x分别为
(
i
′
,
j
)
(i^{'},j)
(i′,j)与
(
i
,
j
′
)
(i,j^{'})
(i,j′)所有取得最小值的分割点中最大的一个。仍需分两种情况讨论，即
z
⩽
y
zleqslant y
z⩽y或
z
>
y
z>y
z>y。
m
(
i
,
j
′
)
+
m
(
i
′
,
j
)
=
w
(
i
,
j
′
)
+
m
(
i
,
z
−
1
)
+
m
(
z
,
j
′
)
+
w
(
i
′
,
j
)
+
m
(
i
′
,
y
−
1
)
+
m
,
(
y
,
j
)
m(i,j^{'})+m(i^{'},j)=w(i,j^{'})+m(i,z-1)+m(z,j^{'})+w(i^{'},j)+m(i^{'},y-1)+m,(y,j)
m(i,j′)+m(i′,j)=w(i,j′)+m(i,z−1)+m(z,j′)+w(i′,j)+m(i′,y−1)+m,(y,j)
因为
z
⩽
y
⩽
j
zleqslant y leqslant j
z⩽y⩽j且
i
<
z
i
第一次放缩时因为
y
y
y是
(
i
′
,
j
)
(i^{'},j)
(i′,j)取得最小值的分割点，却不是
(
i
′
,
j
′
)
(i^{'},j^{'})
(i′,j′)取得最小值时的分割点，
z
z
z是
(
i
,
j
′
)
(i,j^{'})
(i,j′)取得最小值的分割点，却不是
(
i
,
j
)
(i,j)
(i,j)取得最小值的分割点， 因此是放大；第二次放缩是因为
w
w
w的四边形不等式
w
(
i
,
j
)
+
w
(
i
′
,
j
′
)
⩽
w
(
i
,
j
′
)
+
w
(
i
′
,
j
)
w(i,j)+w(i^{'},j^{'})leqslant w(i,j^{'})+w(i^{'},j)
w(i,j)+w(i′,j′)⩽w(i,j′)+w(i′,j)；第三次放缩是因为归纳假设，即
l
<
j
′
−
i
l
第一次放缩时因为
y
y
y是
(
i
′
,
j
)
(i^{'},j)
(i′,j)取得最小值的分割点，却不是
(
i
,
j
)
(i,j)
(i,j)取得最小值时的分割点，
z
z
z是
(
i
,
j
′
)
(i,j^{'})
(i,j′)取得最小值的分割点，却不是
(
i
′
,
j
′
)
(i^{'},j^{'})
(i′,j′)取得最小值的分割点， 因此是放大；第二次放缩是因为
w
w
w的四边形不等式
w
(
i
,
j
)
+
w
(
i
′
,
j
′
)
⩽
w
(
i
,
j
′
)
+
w
(
i
′
,
j
)
w(i,j)+w(i^{'},j^{'})leqslant w(i,j^{'})+w(i^{'},j)
w(i,j)+w(i′,j′)⩽w(i,j′)+w(i′,j)；第三次放缩是因为归纳假设，即
l
<
j
′
−
i
l
综上所述，由数学归纳法即知，
m
(
i
,
j
)
m(i,j)
m(i,j)满足四边形不等式。
s
(
i
,
j
)
⩽
s
(
i
,
j
+
1
)
⩽
s
(
i
+
1
,
j
+
1
)
,
i
⩽
j
s(i,j)leqslant s(i,j+1)leqslant s(i+1,j+1),qquad ileqslant j
s(i,j)⩽s(i,j+1)⩽s(i+1,j+1),i⩽j
证明：当
i
=
j
i=j
i=j时，
s
(
i
,
i
)
⩽
s
(
i
,
i
+
1
)
⩽
s
(
i
+
1
,
j
+
1
)
s(i,i)leqslant s(i,i+1)leqslant s(i+1,j+1)
s(i,i)⩽s(i,i+1)⩽s(i+1,j+1)显然成立。
第一步推导两边同时加上
w
(
i
,
j
)
+
w
(
i
,
j
+
1
)
+
m
(
i
,
k
−
1
)
+
m
(
i
,
k
′
−
1
)
w(i,j)+w(i,j+1)+m(i,k-1)+m(i,k^{'}-1)
w(i,j)+w(i,j+1)+m(i,k−1)+m(i,k′−1)，然后再根据定义合并即可。
m
(
i
,
k
′
)
+
m
(
i
+
1
,
k
)
⩽
m
(
i
+
1
,
k
′
)
+
m
(
i
,
k
)
⇒
w
(
i
,
j
+
1
)
+
m
(
i
,
k
′
)
+
m
(
k
′
+
1
,
j
+
1
)
+
w
(
i
+
1
,
j
+
1
)
+
m
(
i
+
1
,
k
)
+
m
(
k
+
1
,
j
+
1
)
⩽
w
(
i
+
1
,
j
+
1
)
+
m
(
i
+
1
,
k
′
)
+
m
(
k
′
+
1
,
j
+
1
)
+
w
(
i
,
j
+
1
)
+
m
(
i
,
k
)
+
m
(
k
+
1
,
j
+
1
)
⇒
m
k
′
(
i
,
j
+
1
)
+
m
k
(
i
+
1
,
j
+
1
)
⩽
m
k
′
(
i
+
1
,
j
+
1
)
+
m
k
(
i
,
j
+
1
)
m(i,k^{'})+m(i+1,k)leqslant m(i+1,k^{'})+m(i,k)\ Rightarrow qquad w(i,j+1)+m(i,k^{'})+m(k^{'}+1,j+1)+w(i+1,j+1)+m(i+1,k)+m(k+1,j+1)\ leqslant w(i+1,j+1)+m(i+1,k^{'})+m(k^{'}+1,j+1)+w(i,j+1)+m(i,k)+m(k+1,j+1)\ Rightarrow qquad m_{k^{'}}(i,j+1)+m_k(i+1,j+1)leqslant m_{k^{'}}(i+1,j+1)+m_k(i,j+1)
m(i,k′)+m(i+1,k)⩽m(i+1,k′)+m(i,k)⇒w(i,j+1)+m(i,k′)+m(k′+1,j+1)+w(i+1,j+1)+m(i+1,k)+m(k+1,j+1)⩽w(i+1,j+1)+m(i+1,k′)+m(k′+1,j+1)+w(i,j+1)+m(i,k)+m(k+1,j+1)⇒mk′(i,j+1)+mk(i+1,j+1)⩽mk′(i+1,j+1)+mk(i,j+1)
第一步推导两边同时加上
w
(
i
,
j
+
1
)
+
w
(
i
+
1
,
j
+
1
)
+
m
(
k
′
+
1
,
j
+
1
)
+
m
(
k
+
1
,
j
+
1
)
w(i,j+1)+w(i+1,j+1)+m(k^{'}+1,j+1)+m(k+1,j+1)
w(i,j+1)+w(i+1,j+1)+m(k′+1,j+1)+m(k+1,j+1)，然后再根据定义合并即可。
m
i
n
i
<
k
⩽
j
{
m
(
i
,
k
−
1
)
+
m
(
k
,
j
)
}
=
m
i
n
s
(
i
,
j
−
1
)
⩽
k
⩽
s
(
i
+
1
,
j
)
{
m
(
i
,
k
−
1
)
+
m
(
k
,
j
)
}
underset{i#include
O
(
∑
l
e
n
=
2
n
∑
i
=
1
n
−
l
e
n
+
1
(
s
(
i
+
1
,
i
+
l
e
n
−
1
)
−
s
(
i
,
i
+
l
e
n
−
2
)
+
1
)
)
=
O
(
∑
l
e
n
=
2
n
(
s
(
n
−
l
e
n
+
2
,
n
)
−
s
(
1
,
l
e
n
−
1
)
+
n
−
l
e
n
+
1
)
)
=
O
(
∑
l
e
n
=
2
n
n
)
=
O
(
n
2
)
O(sum_{len=2}^{n}sum_{i=1}^{n-len+1}(s(i+1,i+len-1)-s(i,i+len-2)+1))\ =O(sum_{len=2}^{n}(s(n-len+2,n)-s(1,len-1)+n-len+1))\ =O(sum_{len=2}^{n}n)=O(n^2)
O(len=2∑ni=1∑n−len+1(s(i+1,i+len−1)−s(i,i+len−2)+1))=O(len=2∑n(s(n−len+2,n)−s(1,len−1)+n−len+1))=O(len=2∑nn)=O(n2)300
548 592 715 844 602 857 544 847 423 623 645 384 437 297 891 56 963 272 383 477 791 812 528 479 568 392 925 836 71 337 87 648 20 368 832 957 778 140 870 870 978 473 799 800 461 520 780 678 118 720 639 582 143 537 944 758 521 105 414 473 264 186 774 736 456 216 568 135 18 324 617 149 612 222 616 386 943 902 681 449 359 613 437 902 697 99 60 969 666 653 670 170 210 358 128 750 315 607 363 325 570 38 438 634 988 958 102 652 208 635 161 995 653 581 253 414 466 474 244 623 158 338 110 674 656 317 138 778 196 949 368 662 820 13 97 622 837 673 96 971 976 878 468 509 976 55 604 451 739 19 39 441 282 979 120 359 296 480 118 688 317 880 414 918 64 216 692 565 566 865 265 508 523 916 93 921 575 83 929 277 318 9 667 842 131 647 716 841 289 264 183 397 586 552 20 164 828 369 4 146 677 569 270 703 735 288 962 433 248 756 576 396 592 896 572 638 223 891 952 680 447 449 846 978 699 116 297 767 813 411 396 675 881 249 581 313 881 965 692 588 725 659 501 533 956 230 643 394 423 618 606 474 19 470 301 716 660 287 290 383 618 749 428 878 135 102 298 92 569 354 590 551 574 33 653 968 652 320 431 221 896 141 367 97 435 984 891 260 806 537 703 447 100 99 919 352 714 469 998 841
