HDU 2829 Lawrence(斜率优化dp)

题意:

$N\le 1000个点,点权c_i \le 100,划分成0\le M<N个连续段$
$每段的权值w(x, y)=\sum_{i=x}^{y-1}\sum_{j=i+1}^y c_i\cdot c_j$
$求一个划分使得段权值和最小,输出这个权值和$

分析:

$f[j][i]:=前i个点划分成j段的最小权值和$
$f[j][i]=min\{ f[j-1][k]+w(k+1, i) \},然后斜率优化你懂的$
$s_i=\sum_{i=1}^n c_i,s2_i=\sum_{i=1}^n c_i^2$
$w(i, j)=\left((s_j-s_{i-1})^2-(s2_j-s2_{i-1}) \right)/2$
$slope(k, j)\Rightarrow $
$f_j+\left((s_i-s_{j})^2-(s2_i-s2_{j}) \right)/2<f_k+\left((s_i-s_{k})^2-(s2_i-s2_{k}) \right)/2$
$slope(k, j)=\frac{(2f_j+s_j^2+s2_j)-(2f_k+s_k^2+s2_k)}{2(s_j-s_k)}<s_i$
$然后就做完了,时间复杂度O(n^2)$

代码:

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//
// Created by TaoSama on 2016-05-10
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e3 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
typedef long long LL;
int n, m, q[N];
LL f[2][N]; // f[j][i]:= j段到i的最小值
LL s[N], s2[N]; //sum, square sum
//f[j][i] = min { 2f[k] + [ (s[i] - s[k])^2 - (s2[i] - s2[k]) ] / 2 }
//slope(k, j):= { (2f[j]+s[j]*s[j]+s2[j])-(2f[k]+s[k]*s[k]+s2[k]) } /
// { 2(s[j] - s[k]) } <= s[i]
LL up(int p, int k, int j) {
return (2 * f[p][j] + s[j] * s[j] + s2[j]) -
(2 * f[p][k] + s[k] * s[k] + s2[k]);
}
LL dw(int k, int j) {
return 2 * (s[j] - s[k]);
}
bool check(int p, int k, int j, int i) {
return up(p, k, j) * dw(j, i) >= up(p, j, i) * dw(k, j);
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
clock_t _ = clock();
while(scanf("%d%d", &n, &m) == 2 && (n || m)) {
for(int i = 1; i <= n; ++i) {
scanf("%I64d", s + i);
s2[i] = s2[i - 1] + s[i] * s[i];
s[i] += s[i - 1];
// printf("s[%d] = %I64d, s2[%d] = %I64d\n", i, s[i], i, s2[i]);
}
int p = 0;
for(int i = 0; i <= n; ++i) {
f[p][i] = (s[i] * s[i] - s2[i]) / 2;
// printf("f[0][%d] = %I64d\n", i, f[p][i]);
}
for(int j = 1; j <= m; ++j) {
int L = 0, R = 0;
q[R++] = 0;
for(int i = 1; i <= n; ++i) {
while(L + 1 < R && up(p, q[L], q[L + 1]) <= s[i] * dw(q[L], q[L + 1]))
++L;
int k = q[L];
f[!p][i] = f[p][k] + ((s[i] - s[k]) * (s[i] - s[k]) -
(s2[i] - s2[k])) / 2;
while(L + 1 < R && check(p, q[R - 2], q[R - 1], i)) --R;
q[R++] = i;
}
p = !p;
}
printf("%I64d\n", f[p][n]);
}
#ifdef LOCAL
printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
#endif
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到