P4072 [SDOI2016]征途
先推方差：
$$
v m ^ 2 = m \sum x ^ 2 - (\sum x) ^ 2
$$
和是定值不变，考虑使得平方和最小。
$f _ {i, j}$ 表示当前路程 $i$ 分为了 $j$ 段的最小平方和。
易得转移方程：
$$
f _ {i, j} = \min _ {k < i} \{f _ {k, j - 1} + (s[i] - s[k]) ^ 2 \}
$$
其中 $s _ i$ 表示前缀和。
于是可以写出暴力转移的代码，实测可以得到 $90pts$ 。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3e3 + 10, inf = 1e9;
int n, m, w[N], s[N], f[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &w[i]);
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + w[i];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
f[i][j] = inf;
f[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= min(i, m); j++)
for (int k = 0; k < i; k++)
f[i][j] = min(f[i][j], f[k][j - 1] + (s[i] - s[k]) * (s[i] - s[k]));
printf("%d", f[n][m] * m - s[n] * s[n]);
return 0;
}
|
稍稍转化一下式子：
$$
f _ {i, j} - s _ i ^ 2 = \min _ {k < i} \{f _ {k, j - 1} + s _ k ^ 2 - 2 s _ i s _ k \}
$$
记
$$
f _ {i, j} - s _ i ^ 2 = b _ {i, j}
$$
$$
f _ {k, j} + s _ k ^ 2 = y _ {k, j}
$$
$$
2s _ i = k _ i
$$
$$
s _ k = x _ k
$$
那么，方程可以写作
$$
b _ {i, j} = \min _ {k <i} \{y _ {k, j - 1} - k _ ix _ k \}
$$
对于同一个 $j$ ，都从 $j - 1$ 转移，所以先枚举 $j$ 。那么此时 $(x _ k, y _ {k, j - 1})$ 可以看做一个点，答案则为所有的这些点中与 $k$ 确定的直线中截距最小值。即斜率为 $k$ 的直线一直向上平移，在这些点的连线组成的凸包上相交的第一个点即为答案转移的点。
因为 $k = s _ i$ ，即前缀和，随着 $i$ 的增加而增加。可以注意到，前面的点是不可能再相交了。因此可以用单调队列维护当前在凸包上的点。从凸包中删除有两种情况：第一种是它不再是凸包上的点，如果新添加了一个点，使得上一个点是内凹的，那么就将其删除；第二种是不可能成为答案了，当两个凸包上相邻的点的斜率小于直线的斜率时，前一个点一定不如后一个点，那么可以将前一个点删除。
复杂度降为 $O(n m)$ 。
查看代码
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
| #include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3e3 + 10, inf = 1e9;
int hd, tl, q[N];
int n, m, w[N], s[N], f[N][N];
double slope(int x, int a, int b)
{
return (double)(f[a][x] - f[b][x] + s[a] * s[a] - s[b] * s[b]) / (double)(s[a] - s[b]);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &w[i]);
for (int i = 1; i <= n; i++)
s[i] = s[i - 1] + w[i];
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
f[i][j] = inf;
f[0][0] = 0;
for (int i = 1; i <= n; i++)
f[i][1] = s[i] * s[i];
for (int j = 2; j <= m; j++)
{
hd = 1, tl = 0;
for (int i = 1; i <= n; i++)
{
while (hd < tl && slope(j - 1, q[hd], q[hd + 1]) < s[i] * 2)
hd++;
f[i][j] = f[q[hd]][j - 1] + (s[q[hd]] - s[i]) * (s[q[hd]] - s[i]);
while (hd < tl && slope(j - 1, q[tl - 1], q[tl]) > slope(j - 1, q[tl], i))
tl--;
q[++tl] = i;
}
}
printf("%d", f[n][m] * m - s[n] * s[n]);
return 0;
}
|