HDU 3480 DP 斜率优化 Division

把n个数分成m段，每段的值为(MAX - MIN)²，求所能划分得到的最小值。

依然是先从小到大排个序，定义状态d(j, i)表示把前i个数划分成j段，所得到的最小值，则有状态转移方程：

d(j, i) = min { d(j-1, k) + (a_i - a_k+1)² | 0 ≤ k < i }

设 l < k < i，且由k转移得到的状态比由l转移得到的状态更优。

有不等式：

$d(j-1,l)+(a_i-a_{l+1})^2geq d(j-1,k)+(a_i-a_{k+1})^2$

整理成斜率形式：

$frac{left[d(j-1,l)+{a_{l+1}}^2 ight ]-left[d(j-1,k)+{a_{k+1}}^2 ight ]}{a_{l+1}-a_{k+1}}leq 2a_i$

后面的就可以相当于套模板了，不过这里要用滚动数组优化一下空间。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 10000 + 10;
 8 const int maxm = 5000 + 10;
 9 const int INF = 0x3f3f3f3f;
10 
11 int n, m;
12 
13 int a[maxn];
14 int d[2][maxn];
15 
16 int head, tail;
17 int Q[maxn];
18 
19 int cur;
20 
21 int inline Y(int x) { return d[cur^1][x] + a[x+1] * a[x+1]; }
22 
23 int inline DY(int p, int q) { return Y(q) - Y(p); }
24 
25 int inline DX(int p, int q) { return a[q+1] - a[p+1]; }
26 
27 int main()
28 {
29     freopen("in.txt", "r", stdin);
30 
31     int T; scanf("%d", &T);
32     for(int kase = 1; kase <= T; kase++)
33     {
34         scanf("%d%d", &n, &m);
35         for(int i = 1; i <= n; i++) scanf("%d", a + i);
36         sort(a + 1, a + 1 + n);
37 
38         memset(d[0], 0x3f, sizeof(d[0]));
39         d[0][0] = 0;
40         cur = 0;
41         for(int i = 1; i <= m; i++)
42         {
43             cur ^= 1;
44             head = tail = 0;
45             Q[tail++] = 0;
46             for(int j = 1; j <= n; j++)
47             {
48                 while(head + 1 < tail && DY(Q[head], Q[head+1]) <= DX(Q[head], Q[head+1]) * 2 * a[j]) head++;
49                 while(head + 1 < tail && DY(Q[tail-1], j) * DX(Q[tail-2], Q[tail-1]) <= DY(Q[tail-2], Q[tail-1]) * DX(Q[tail-1], j)) tail--;
50                 Q[tail++] = j;
51                 d[cur][j] = d[cur^1][Q[head]] + (a[j]-a[Q[head]+1]) * (a[j]-a[Q[head]+1]);
52             }
53         }
54         printf("Case %d: %d
", kase, d[cur][n]);
55     }
56 
57     return 0;
58 }

代码君

下面是四边形不等式优化的代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 10000 + 10;
 8 const int maxm = 5000 + 10;
 9 const int INF = 0x3f3f3f3f;
10 
11 int n, m;
12 
13 int a[maxn];
14 int d[maxm][maxn], s[maxm][maxn];
15 
16 int main()
17 {
18     int T; scanf("%d", &T);
19     for(int kase = 1; kase <= T; kase++)
20     {
21         scanf("%d%d", &n, &m);
22 
23         for(int i = 1; i <= n; i++) scanf("%d", a + i);
24         sort(a + 1, a + 1 + n);
25 
26         memset(s, 0, sizeof(s));
27         for(int i = 1; i <= m; i++)
28         {
29             int j;
30             for(j = 1; j <= i; j++) d[i][j] = 0;
31             for(; j <= n; j++) d[i][j] = INF;
32         }
33 
34         for(int i = 1; i <= n; i++)
35         {
36             s[1][i] = 0;
37             d[1][i] = (a[i] - a[1]) * (a[i] - a[1]);
38         }
39 
40         for(int i = 2; i <= m; i++)
41         {
42             s[i][n+1] = n;
43             for(int j = n; j > i; j--)
44             {
45                 for(int k = s[i-1][j]; k <= s[i][j+1]; k++)
46                 {
47                     int t = d[i-1][k] + (a[j] - a[k+1]) * (a[j] - a[k+1]);
48                     if(t < d[i][j])
49                     {
50                         d[i][j] = t;
51                         s[i][j] = k;
52                     }
53                 }
54             }
55         }
56 
57         printf("Case %d: %d
", kase, d[m][n]);
58     }
59 
60     return 0;
61 }

代码君