Codeforces Round #715 (Div. 2)
C. The Sports Festival
题目:给你一个数组
a
i
ai
ai,定义
d
i
=
m
a
x
(
a
1
,
a
2..
,
a
i
)
−
m
i
n
(
a
1
,
a
2...
,
a
i
)
.
di=max(a1,a2..,ai)-min(a1,a2...,ai).
di=max(a1,a2..,ai)−min(a1,a2...,ai).,让你最小化
∑
1
n
d
i
\sum_1^ndi
∑1ndi.
你可以对数组上的元素任意地安排它的位置.
思路:先不考虑如何去安排,想像一下如何求出这个
d
i
di
di较为方便.
对
a
i
ai
ai进行排序后,显然
d
i
=
a
i
−
a
1
di=ai-a1
di=ai−a1.
对于每一个
d
i
di
di,如何才能使得它的值变的更小呢.显然和当前最小的元素和最大的元素有关,要么是
a
1
a1
a1放到
[
i
+
1
,
n
]
上
,
要
么
就
是
把
a
i
放
到
[
i
+
1
,
n
]
上
[i+1,n]上,要么就是把ai放到[i+1,n]上
[i+1,n]上,要么就是把ai放到[i+1,n]上.但是这样做会影响到区间
[
i
+
1
,
n
]
上
的
d
i
的
取
值
[i+1,n]上的di的取值
[i+1,n]上的di的取值
上述思想启发我们,应该使用区间动态规划解决上述的影响.
d
p
(
l
,
r
)
代
表
该
区
间
上
的
∑
i
=
l
n
d
i
的
最
小
值
dp(l,r)代表该区间上的\sum_{i=l}^ndi的最小值
dp(l,r)代表该区间上的∑i=lndi的最小值
d
p
(
l
,
r
)
=
a
r
−
a
l
+
m
i
n
(
d
p
(
l
+
1
,
r
)
,
d
p
(
l
,
r
−
1
)
)
dp(l,r)=a_r-a_l+min(dp(l+1,r),dp(l,r-1))
dp(l,r)=ar−al+min(dp(l+1,r),dp(l,r−1))
dp式子是如何推出来的呢,观察长度为3的区间:
a
1
,
a
2
,
a
3
(
a
1
<
a
2
<
a
3
)
a1,a2,a3(a1
