C. The Sports Festival

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 ∑1n​di. 你可以对数组上的元素任意地安排它的位置. 思路:先不考虑如何去安排,想像一下如何求出这个 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=ln​di的最小值 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