题目链接
题目
题意
给出一个长度为$n$的整数序列$a$， 将$a$重排， 设$d_i = max \{a_1, a_2, … a_i \} - min \{a_1, a_2, … a_i \}$， 最小化$\sum_{i = 1}^n d_i$
数据范围
$1 \leq n \leq 2000, 1 \leq a_i \leq 10^9$
题解
解法1
显然是区间dp题
设$mx_i = max \{a_1, a_2, … a_i \}, mn_i = min \{a_1, a_2, … a_i \}$
如果我们排好的序列中， 有一个$mx_i = mx_{i - 1}, mn_i = mn_{i - 1}, a_i \neq a_{i - 1}$， 那么这个序列肯定不会是最优的， 因为交换$a_i, a_{i - 1}$会得到更优的答案
也就是说我们每次确定$a_i$时， 如果$a_i \neq a_{i - 1}$， 那$mx, mn$必须要改变一个
那么思路就有了， 我们将$a$数组从小到大排好序， 然后枚举一个$len$， 让前$len$个数作为$mn$倒序依次出现， 剩下的数作为$mx$依次出现， 然后就是区间dp了
但是这样做显然是$O(n^3)$的， 过不了$2000$的数据
优化
直觉告诉我从中间分开是最优的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include <iostream>
#include <cstdio>
#include <algorithm>
int n;
int a[2003];
int mn[1003], mx[1003];
long long f[1003][1003], ans;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
std:: sort(a + 1, a + n + 1);
int mid = n / 2;
if(mid * 2 == n)
{
for(int i = 1; i <= mid; i ++)
mn[i] = a[i], mx[i] = a[i + mid];
std:: reverse(mn + 1, mn + mid + 1);
f[1][1] = mx[1] - mn[1];
for(int i = 2; i <= mid; i ++)
f[1][i] = f[1][i - 1] + mx[i] - mn[1], f[i][1] = f[i - 1][1] + mx[1] - mn[i];
for(int i = 2; i <= mid; i ++)
for(int j = 2; j <= mid; j ++)
f[i][j] = std:: min(f[i - 1][j], f[i][j - 1]) + mx[j] - mn[i];
ans = f[mid][mid];
}
else
{
for(int i = 1; i <= mid; i ++)
mn[i] = a[i], mx[i] = a[i + mid];
mx[mid + 1] = a[n];
std:: reverse(mn + 1, mn + mid + 1);
f[1][1] = mx[1] - mn[1];
for(int i = 2; i <= mid; i ++)
f[1][i] = f[1][i - 1] + mx[i] - mn[1], f[i][1] = f[i - 1][1] + mx[1] - mn[i];
f[1][mid + 1] = f[1][mid] + mx[mid + 1] - mn[1];
for(int i = 2; i <= mid; i ++)
for(int j = 2; j <= mid + 1; j ++)
f[i][j] = std:: min(f[i - 1][j], f[i][j - 1]) + mx[j] - mn[i];
ans = f[mid][mid + 1];
for(int i = 1; i <= mid; i ++)
mn[i] = a[i], mx[i] = a[i + mid + 1];
mn[mid + 1] = a[mid + 1];
std:: reverse(mn + 1, mn + mid + 2);
f[1][1] = mx[1] - mn[1];
for(int i = 2; i <= mid; i ++)
f[1][i] = f[1][i - 1] + mx[i] - mn[1], f[i][1] = f[i - 1][1] + mx[1] - mn[i];
f[mid + 1][1] = f[mid][1] + mx[1] - mn[mid + 1];
for(int i = 2; i <= mid + 1; i ++)
for(int j = 2; j <= mid; j ++)
f[i][j] = std:: min(f[i - 1][j], f[i][j - 1]) + mx[j] - mn[i];
ans = std:: min(ans, f[mid + 1][mid]);
}
printf("%lld\n", ans);
return 0;
}
|
肯定不对， wa
继续优化
按照我们一开始的思路， $f$数组初始化应该先选择$a_{len}, a_{len + 1}$， 然后$i$从$len - 1$到$1$， $j$从$len + 2$到$n$， $f[i][j] = min(f[i + 1][j], f[i][j - 1]) + a[j] - a[i]$， 这实际上是选择一个中点， 然后向两边拓展， 枚举中点$O(n)$， 向两边拓展$O(n^2)$， 总体$O(n^3 + nlog)$
那如果我们反过来呢？
上述的dp思路由于选择的中点不同导致初始状态不同， 所有不同中点的dp过程中没有公共子问题重叠， 观察到虽然他们的起点不一样， 但是终点都是$f[1][n]$
那我们考虑从两边往中间拓展， 这样初始状态就一样了， 存在了子问题重叠， 按照正常顺序添加的话$a_1, a_n$肯定会放在最后边， 而且一定会造成$a_n - a_1$的贡献，而且要保证每次添加$mx, mn$至少一个发生变化， 两边还是要按顺序添加的 ， 尽量让最大/最小极值尽可能在后面出现， 所以我们实际上就是在倒着模拟整个添加过程， 在过程中dp， 肯定是正确的
最后$O(n)$枚举中点， 这样时间复杂度就变成了$O(n^2 + nlog + n)$， $2000$稳过
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <iostream>
#include <cstdio>
#include <algorithm>
int n;
int a[2003];
long long f[2003][2003], ans = 1e18;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
std:: sort(a + 1, a + n + 1);
for(int i = n; i > 1; i --) f[1][i] = f[1][i + 1] + a[i] - a[1];
for(int i = 1; i < n; i ++) f[i][n] = f[i - 1][n] + a[n] - a[i];
for(int i = 2; i < n; i ++)
for(int j = n - 1; j > i; j --)
f[i][j] = std:: min(f[i - 1][j], f[i][j + 1]) + a[j] - a[i];
for(int i = 1; i < n; i ++) ans = std:: min(ans, f[i][i + 1]);
printf("%lld\n", ans);
return 0;
}
|
DP
种类很多， 优化也多样， 还没怎么学， 目前只能凭感觉优化