Description
Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v，可以证明，v×m^2是一个整数。为了避免精度误差，输出结果时输出v×m^2。
第一行两个数 n、m。
第二行 n 个数，表示 n 段路的长度
Output
一个数，最小方差乘以 m^2 后的值
5 2
1 2 5 8 6
Sample Output
36
HINT
1≤n≤3000,保证从 S 到 T 的总路程不超过 30000
Solution
滚动数组+斜率优化DP。
我们要最小化方差，化简方差的式子，可以得到我们实际上在最小化这m段平方和。
记录这道题的原因是，终于对斜率优化有点明白了QAQ，以前搞不懂为什么要在队列头处找到一条直线斜率要大于Si，现在终于懂了，我对于这个的理解是因为Si是递增的嘛，所以如果这条直线不满足大于Si的条件，那么对于以后的Si，这条直线势必不会满足了。还有我们可以开两个数组，分别存DP中这一行和上一行的值，更新的时候用上一行的更新这一行的，来实现滚动数组。
注意这道题数据貌似是有问题，蒟蒻也没使用getint加速IO，直接scanf读入/读出了。
速度好慢QAQ
貌似wordpress终于资瓷markdown编辑了（尽管hexo一直资瓷markdown）！嗨皮~
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1009999999;
const int maxn = 3005;
int n, m;
int Q[maxn], head, tail;
LL wa[maxn], S[maxn], wb[maxn];
LL *dp, *dpn, *t;
double UP(int i, int j) { return double(dp[i]) + double(S[i]) * S[i] - double(dp[j]) - double(S[j]) * S[j]; }
double DOWN(int i, int j) { return double(S[i] - S[j]) * 2; }
double K(int i, int j) { return UP(i, j) / DOWN(i, j); }
int main() {
scanf("%d%d", &n, &m);
dp = wa; dpn = wb;
for (int i = 1; i <= n; ++i) {
scanf("%lld", S + i);
S[i] += S[i-1];
dpn[i] = S[i] * S[i];
}
for (int k = 1; k < m; ++k) {
t = dp; dp = dpn; dpn = t;
head = 0; tail = 0; Q[0] = 0;
for (int i = 1; i <= n; ++i) {
while (head < tail && K(Q[head + 1], Q[head]) < double(S[i]))
++head;
dpn[i] = dp[Q[head]] + (S[i] - S[Q[head]]) * (S[i] - S[Q[head]]);
while (head < tail && K(i, Q[tail]) <= K(Q[tail], Q[tail - 1]))
--tail;
Q[++tail] = i;
}
}
LL ans = dpn[n] * m - S[n] * S[n];
printf("%lld", ans);
return 0;
}
|