題意：
n個(gè)點(diǎn)，用水平線或者豎直線劃分成k條，要求平均差最小，平均差為每條中點(diǎn)的個(gè)數(shù)減去n/k的絕對(duì)值。
解法：
首先一看就是個(gè)DP，與處理不說了，用水平掃描線、豎直掃描線將同一直線上的點(diǎn)壓縮成一個(gè)帶權(quán)值的點(diǎn)，然后DP
這題重要的是DP降維
觀察DP方程
dp[i]=min{dp[j]+|sum[i]-sum[j]-average|}
這里就要分成兩部分討論
1、當(dāng)sum[i]-sum[j]>average時(shí)
dp[i]=min{dp[j]+sum[i]-sum[j]-average}
這就是一個(gè)變量“打擂臺(tái)”的問題，從前向后掃，維護(hù)一個(gè)dp[j]-sum[j]的最小值即可。
2、當(dāng)sum[i]-sum[j]<average時(shí)
dp[i]=min{dp[j]+average-sum[i]+sum[j]}
這里打擂臺(tái)就不行了，因?yàn)閰^(qū)間是移動(dòng)著的。開始偷懶，直接用STL的set動(dòng)態(tài)維護(hù)一個(gè)dp[j]+sum[j]的最小值。。果斷TLE。。汗。。
木辦法。。化簡(jiǎn)方程吧
把sum[j]看作橫坐標(biāo)，dp[j]看作縱坐標(biāo)，轉(zhuǎn)化為斜率優(yōu)化問題
dp[j]=-sum[j]+sum[i]-average+dp[i]
令sum[i]-average+dp[i]=A
方程化為
dp[j]=-sum[j]+A
為了讓A最小，就是找到個(gè)j，使得dp[j]+sum[j]最小，然后就是斜率優(yōu)化的經(jīng)典方法了，用棧隊(duì)列
當(dāng)dp[k]+sum[k]>dp[j]+sum[j],j>k的時(shí)候，k退棧，然后將j壓棧
在棧的底端，將不符合要求的狀態(tài)，即sum[i]-sum[j]>average,i>j的隊(duì)頭狀態(tài)j給出隊(duì)。這樣，隊(duì)頭的元素就為最優(yōu)值
所有元素頂多進(jìn)隊(duì)一次，出隊(duì)一次，復(fù)雜度O(n)
總復(fù)雜度為O(k*m)
不知道怎么回事。。在POJ上死都TLE。。本機(jī)秒解，HDU500MS，可能分?jǐn)?shù)類寫的有點(diǎn)搓了。。把代碼貼出來，大家看看哪里能修正修正。。。好想好想把poj給過了啊。
1
# include <cstdio>
2using namespace std;
3# include <vector>
4# include <algorithm>
5# include <utility>
6# include <functional>
7# include <map>
8# include <cstring>
9# define abs(num) ((num)>0?(num):-(num))
10# define eps 1e-6
11struct func
12
{
13
int up,down;
14
func(){}
15 func(int num):up(num),down(1){}
16 int gcd(int a,int b)
17 {
18 if(!b) return a;
19 else return gcd(b,a%b);
20
}
21 void simple()
22 {
23 int t=gcd(abs(up),abs(down));
24 up/=t;
25 down/=t;
26 if(down<0) up*=-1,down*=-1;
27 }
28 func operator+(const func &pos)
29 {
30 func res;
31 res.down=down*pos.down;
32 res.up=up*pos.down+pos.up*down;
33 res.simple();
34 return res;
35 }
36 func operator-(const func &pos)
37 {
38 func res;
39 res.down=down*pos.down;
40 res.up=up*pos.down-pos.up*down;
41 res.simple();
42 return res;
43 }
44 bool operator<(const func &pos) const
45 {
46 return up*pos.down<pos.up*down;
47 }
48 bool operator==(const func &pos) const
49 {
50 return up==pos.up&&down==pos.down;
51 }
52 bool operator!=(const func &pos) const
53 {
54 return up!=pos.up||down!=pos.down;
55 }
56 bool operator<=(const func &pos) const
57 {
58 return *this<pos||*this==pos;
59 }
60
61
};
62int data[100000],de;
63func dp[10][100000];
64func aver;
65int k;
66int q[100000];
67func num[100000];
68struct cmp
69{
70 bool operator()(const pair<int,int> &a,const pair<int,int> &b) const
71 {
72 if(dp[a.first][a.second]+func(data[a.second])!=dp[b.first][b.second]+func(data[b.second]))
73 return dp[a.first][a.second]+func(data[a.second])<dp[b.first][b.second]+func(data[b.second]);
74 else return a.second<b.second;
75 }
76};
77func min(func a,func b)
78{
79 if(a.up*b.down<b.up*a.down) return a;
80 else return b;
81}
82func solve()
83{
84 for(int i=0;i<de;i++)
85 num[i]=func(data[i]);
86 int down=aver.up/aver.down,up=aver.up%aver.down?aver.up/aver.down+1:aver.up/aver.down;
87 for(int i=0;i<de;i++)
88 if(data[i]<=down) dp[0][i]=aver-num[i];
89 else dp[0][i]=num[i]-aver;
90 for(int i=1;i<k;i++)
91 {
92 for(int j=0;j<de;j++)
93 dp[i][j]=dp[i-1][j]+aver;
94 int last=-1;
95 func ans=func(0xfffffff);
96 for(int j=0;j<de;j++)
97 {
98 while(data[j]-data[last+1]>=up)
99 {
100 last++;
101 if(!last) ans= dp[i-1][last]-num[last]-aver;
102 else ans=min(ans,dp[i-1][last]-num[last]-aver);
103 }
104 if(last!=-1)
105 dp[i][j]=min(dp[i][j],ans+num[j]);
106
107 }
108 int s=-1,e=0;
109 q[0]=0;
110 for(int j=1;j<de;j++)
111 {
112 //add
113 while(s!=e&&dp[i-1][j]+num[j]<=dp[i-1][q[e]]+num[q[e]])
114 e--;
115 q[++e]=j;
116 //erase
117 while(s!=e&&data[j]-data[q[s+1]]>down) s++;
118 if(s!=e)
119 dp[i][j]=min(dp[i][j],dp[i-1][q[s+1]]+aver-num[j]+num[q[s+1]]);
120
121 }
122 }
123 return dp[k-1][de-1];
124
125}
126int main()
127{
128 //freopen("land.in","r",stdin);
129 //freopen("ans.txt","w",stdout);
130 pair<int,int> d[100000];
131 map<int,int> refer;
132 int n,test=1;
133 while(scanf("%d%d",&n,&k)!=EOF&&(n||k))
134 {
135 refer.clear();
136 aver.up=n;
137 aver.down=k;
138 aver.simple();
139 for(int i=0;i<n;i++)
140 scanf("%d%d",&d[i].first,&d[i].second);
141 for(int i=0;i<n;i++)
142 refer[d[i].first]++;
143 data[0]=0;
144 de=1;
145 for(map<int,int>::iterator i=refer.begin();i!=refer.end();i++)
146 data[de++]=(i->second);
147 for(int i=1;i<de;i++)
148 data[i]+=data[i-1];
149
150 func ans=solve();
151 refer.clear();
152 for(int i=0;i<n;i++)
153 refer[d[i].second]++;
154 data[0]=0;
155 de=1;
156 for(map<int,int>::iterator i=refer.begin();i!=refer.end();i++)
157 data[de++]=(i->second);
158 for(int i=1;i<de;i++)
159 data[i]+=data[i-1];
160 ans=min(ans,solve());
161 ans.down*=k;
162 ans.simple();
163 printf("%d. %d/%d\n",test++,ans.up,ans.down);
164 }
165 return 0;
166}
。