Description
给你两个正整数 $n$ 和 $m$ ，以及 $n$ 个递增的正整数 $x_i$ ，你可以将 $m$ 个递增的 $p_i$ 设为在 $1$ 到 $n$ 之间且两两不同的整数，请你求出 $\sum_{i = 1} ^ n \min \{ { |x_i - x_{p_j} | (1 \leq j \leq m)} \}$ 的最小值。
Solution
考虑使用 DP 来解题，设 $f_{i, j}$ 表示 $p_1$ ~ $p_j$ 的值已经确定了，并且 $p_j = i$ 。
转移方程易得。
但是 $f_{n, m}$ 并不一定是答案，因为 $p_m$ 不一定等于 $n$ 。
答案其实是 $\min_{i = m} ^ n [f_{i, m} + \sum_{j = i + 1} ^ n (x_j - x_i)]$ 。
DP 时可以设 $g_{i, j}$ 来表示 $p_{a} = i$ ， $p_{a - 1} = j(a \geq 2)$ 时所需的代价来辅助 DP ，预处理的时间复杂度是 $O(n ^ 3)$ 的。
DP 部分的复杂度则为 $O(n ^ 2 m)$ 。
然后我们就得到了一个 $O(n ^ 3)$ 的算法了。
Code
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
| #include <cstdio>
#include <cstring>
#define maxN 310
#define maxM 40
int f[maxN][maxM];
int g[maxN][maxN], a[maxN];
int min (int x, int y)
{
return x < y ? x : y;
}
int main ()
{
int n = 0, m = 0;
scanf("%d %d", &n, &m);
for(int i = 1;i <= n; i++)
{
scanf("%d", &a[i]);
}
for(int i = 1;i <= n; i++)
{
for(int j = 0;j < i; j++)
{
for(int k = j + 1;k < i; k++)
{
if(!j)
{
g[i][j] += a[i] - a[k];
continue;
}
g[i][j] += min(a[k] - a[j], a[i] - a[k]);
}
}
}
memset(f, 127 / 3, sizeof(f));
f[0][0] = 0;
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= m; j++)
{
for(int k = j - 1;k < i; k++)
{
f[i][j] = min(f[i][j], f[k][j - 1] + g[i][k]);
}
}
}
int ans = 2147483647;
for(int i = m;i <= n; i++)
{
int da = f[i][m];
for(int j = i + 1;j <= n; j++)
{
da += a[j] - a[i];
}
ans = min(ans, da);
}
printf("%d", ans);
return 0;
}
|