感覺以前很少接觸到這種劃分的問題，但是它又好像很經典的樣子。
本題要求劃分的 k 塊之間盡量一樣。使他們的平均偏差最小。 可以很容易想到o(n^2)的dp。然后經隊友提醒，采用單調隊列優化到o(n)。o(n^2)的dp可以這樣考慮：當第 i 根劃分線緊跟在坐標 j 之后時， 枚舉第 i-1 根劃分線在前面的哪個位置然后轉移。 要把這個dp降一維，首先要去掉絕對值。可以通過分類討論來去掉絕對值。
可以想像有一個滑動窗口（綠色），窗口內的轉移項始終保持最后一項小于平均值。那么窗口左邊的就始終大于平均值。這樣絕對值就去掉了。然后維護一個滑動窗口里的單調隊列就可以了。
1 #include <string>
2 #include <vector>
3 #include <map>
4 #include <cstdlib>
5 #include <cstring>
6 #include <cassert>
7 #include <set>
8 #include <iostream>
9 #include <sstream>
10 #include <cstddef>
11 #include <algorithm>
12 #include <utility>
13 #include <iterator>
14 #include <numeric>
15 #include <list>
16 #include <complex>
17 #include <cstdio>
18 #include <climits>
19 #include <cassert>
20
21
22 using namespace std;
23
24 const int maxn = 100100;
25
26 int gcd(int a, int b){return b ? gcd(b, a%b) : a; }
27
28 int X[maxn], Y[maxn], V[maxn];
29 int dp[12][maxn];
30
31 int N, K;
32
33 int que[maxn], bb, ee;
34 int minx, nowx;
35
36 void init()
37 {
38 minx = -1;
39 nowx = 0;//最小的當前仍然滿足和 < N的下標
40 bb = 0;
41 ee = 0;
42 }
43
44 int solve(int X[])
45 {
46 sort(X, X + N);
47
48 V[0] = 0;
49 int cnt = 1, pre = -1;
50 for(int i = 0; i < N; i++)
51 {
52 if(X[i] == pre)
53 V[cnt-1]++;
54 else
55 {
56 V[cnt++] = 1;
57 pre = X[i];
58 }
59 }
60
61 //V[0]不是實際的點，是臨時加的點
62 for(int i = 1; i < cnt; i++)
63 {
64 V[i] += V[i-1];
65 }
66
67 for(int i = 0; i < cnt; i++)
68 {
69 V[i] *= K; // 擴大倍數，沒有分母
70 }
71
72 for(int i = 0; i < cnt; i++)
73 {
74 dp[1][i] = abs(V[i] - N);
75 }
76
77
78 for(int i = 2; i <= K; i++)
79 {
80 init();
81 for(int j = 0; j < cnt; j++)
82 {
83 while(V[j] - V[nowx] >= N)
84 {
85 if(minx==-1 || dp[i-1][minx] + V[nowx] - V[minx]> dp[i-1][nowx])
86 minx = nowx;
87 nowx++;
88 }
89
90 while(bb != ee && que[bb] < nowx)bb = (bb+1)%maxn;
91
92 while(bb != ee)
93 {
94 int lastid = ( ee - 1 + maxn ) % maxn;
95 int last = que[lastid];
96 if(dp[i-1][last] - ( V[j] - V[last]) < dp[i-1][j] )break;
97 ee = lastid;
98 }
99 que[ee] = j;
100 ee = ( ee + 1 ) % maxn;
101
102 assert(bb != ee);
103
104 dp[i][j] = dp[i-1][que[bb]] + N - ( V[j] - V[que[bb]] );
105
106 if(minx != -1)
107 dp[i][j] = min( dp[i][j], dp[i-1][minx] + V[j] - V[minx] - N );
108 }
109 }
110
111 return dp[K][cnt-1];
112 }
113
114 int main()
115 {
116 int cas = 1;
117 while(scanf("%d %d",&N, &K) != EOF)
118 {
119 if(N == 0 && K == 0)break;
120 for(int i = 0; i < N; i++)
121 {
122 scanf("%d %d",&X[i], &Y[i]);
123 }
124
125 int n = min( solve(X), solve(Y) );
126 int d = K*K;
127 int g = gcd(n, d);
128 printf("%d. %d/%d\n",cas++, n / g, d / g);
129 }
130 }
posted on 2010-07-18 16:21
wangzhihao 閱讀(249)
評論(0) 編輯 收藏 引用 所屬分類:
單調隊列