先把位置排序,保存在p数组中

用一个list数组表示如果一个邮局覆盖了从i到j的村庄，那么最小距离是多少，

则list=list+p[j]-p[i];(中位数)

用dp表示前i个邮局覆盖了前j个村庄时最小距离是多少，只需枚举最后一个邮局覆盖的村庄，即

dp=min(dp+list[k+1,j]) (0

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

秒杀！（虽然交了3次 囧....)

初始化 2个for f:=maxlongint；

枚举有i个邮局时，第i个邮局放在k时，前j个村庄去邮局的最短距离。

m*n^2...

楼下的楼下正解。。

那个方程的确是有后效性的

但由于后效性不会使答案变小

算法又能在别的情况下枚举到最优解

所以

这题还是可以用简单的石子归并做的

大家的思路各不相同啊，都是大牛啊！

我的思路就是如果在i,j分别放一个邮局，中间我再放别的邮局，那么中间的这些点一定是到i的或到j，根据这个就可以A了这个题了

f[i][j]=min{f[k][j-1]+w[k+1,i]}

这个方程是有后效性的，也就是说在后面分组的时候，有可能新建的邮局到这组以前村庄的距离小于那个村庄到它当时那个邮局的距离，也就是有村庄选择了更远的邮局，那么这时一定不是最优解。可以肯定最优解的值是唯一的，最小的，这个算法一定可以枚举出最优解所在的分组方案，所以虽然有后效性但却是正确的

感谢walala的题解

DP+中位数的知识

var

a:array[0..300,0..300]of longint;

b:array[1..300,1..30]of longint;

c:array[1..300]of longint;

n,m,i,k,j:longint;

begin

readln(n,m);

for i:=1 to n do read(c[i]);

for i:=1 to n do

for j:=i to n do

for k:=i to j do a:=a+abs(c[k]-c[(i+j)div 2]);

fillchar(b,sizeof(b),1);

for i:=1 to n do b:=a[1,i];

for i:=2 to m do

for j:=1 to n do

for k:=1 to j do

if b[k,i-1]+a[k+1,j]

//p1242

var

a : array[1..400] of longint;

g, f : array[0..1000,0..1000] of longint;

i, j, k, n, m, mid : longint;

begin

assign(input, 'p1242.in'); reset(input);

assign(output, 'p1242.out'); rewrite(output);

readln(n, m);

for i := 1 to n do

read(a[i]);

fillchar(f, sizeof(f),$7f);

for i := 1 to n do

for j := i to n do

begin

mid := a[(i + j) div 2];

g[i, j] := 0;

for k := i to j do

g[i, j] := g[i, j] + abs(mid - a[k]);

end;

for i := 0 to n do

f[i, 0] := 0;

for j := 0 to n do

f[0, j] := 0;

for i := 1 to n do

for j := 1 to m do

begin

for k := j-1 to i-1 do

if f[i, j] > f[k, j-1] + g[k+1, i] then

begin

f[i, j] := f[k, j-1] + g[k+1, i];

end;

end;

writeln(f[n, m]);

close(input);

close(output);

end.

Accepted 有效得分：100 有效耗时：0ms

DP+预处理

l[i][j]表示在第i,i+1,i+2...,j个村庄间放一个邮局,这些村庄到邮局的距离和

x[i][j]表示前i个村庄,放了j个邮局的最小和

x[i][j]=min(x[k][j-1]+l[k+1][i]); {k=1,2,....i}

x[n][m]就是答案了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

要有预处理。

不用输出方案就好做多了，直接DP记录最优解，OVER。

f:=Min{f[k,j-1]+cost[k+1,i]}

因为有中位数这个好东西所以避免了在cost里面二重动归哦哈哈哈！

解题报告 http://plfxy.blog.hexun.com/24789682_d.html

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

任意两个村庄的距离d（中位数求） + 一维数组滚动求最值 = 24行的程序 + 0ms AC

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

水题一道，宋方睿败鄙视我。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

1次秒杀IOI~~~~~~~~~~~~~

先计算出每一段只建一个邮局的最小值(f)，显然是在中位数上

best=min(best[k,j-1]+f[k+1,i]);

(1

如果只能建一个邮局，很显然应该建在中位数上

设f[m,n]为前n个村庄建m个邮局，然后枚举第m个邮局管哪些村庄

O(mn^2)

四边形不等式后

O(mn)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

ff(a,b)表示前a个村庄建立b个邮局的最优值！

kk[i]表示i到b这段村庄建一个邮局的最优 预处理得到

int ff(int a,int b){

int tmp=9999999;

if(rec[a]!=0)

return rec[a];

if(b==0) return 0;///注意这个 一定要先返回这个

if(a==0) return 9999999;

for(int i=a;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 9ms

├ 测试数据 06：答案正确... 25ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：34ms

纪念一下···

主要处理好区间内有1个邮局的最小····

加个四边形不等式优化...0ms。AC

Program Post;

Const

Maxn = 301;

Var

Data: Array [0..1, 1..Maxn] Of Longint;

a: Array [1..Maxn] Of Integer;

t: Array [0..Maxn] Of Longint;

s: Array [1..Maxn, 1..Maxn] Of Longint;

v, p, n, i, j, k: Integer;

Min, Mink: Longint;

Begin

ReadLn(v, p);

For i:=1 To v Do Read(a[i]);

T[0] := 0;

For i:= 1 To v Do T[i] := T + a[i];

For i:= 1 To v Do

For j:= i To v Do Begin

k := (i + j) Div 2;

If (i + j) Mod 2=0

Then s[i, j] := T[j] - T[k] - T[k-1] + T[i - 1]

Else s[i, j] := T[j] - T[k] - T[k] + T[i - 1];

End;

Fillchar(Data, SizeOf(Data), 0);

n := 0;

For i:=1 To v Do Data[0, i] := s[1, i];

For i:= 2 To p Do Begin

For j:= i To v Do Begin

Min := MaxLongint;

For k:=i-1 To j-1 Do Begin

Mink := Data[n, k] + s[k + 1, j];

If Min > Mink Then Min := Mink;

End;

Data[1 - n, j] := Min;

End;

n := 1 - n;

End;

WriteLn(Data[n, v]);

End.