感觉dp的状态及方程最重要,边界最难整.

膜拜fjxmlhx教主

事实上，枚举邮局放的位置，然后每两个邮局之间的村庄必定选择这两个邮局之一。。那么就可以DP了

f表示前一个邮局放在第I个位置，还剩下j个邮局。

决策就是枚举下一个邮局在哪里即可。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

原来数组开小了的结果是………………答案错误！！

又见中位数

mmd，原来想拿这道题先热身的

结果做了1小时........

严重bs评测机的稳定性！两次提交同样的程序

村庄坐标不用排序。

给前i个村庄分j个邮局：

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

cost：给从第k+1到第i个村庄分一个邮局的最小距离和

编译通过...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

中点(众数)

原来IOI2000与NOIP2000一脉相承……

感谢楼下自由狂想论提醒！！

切记:

第I到第J个村庄中间建1个邮箱不要建在 第I个村庄到第J个村庄距离的中点上,而要建在 第I个村庄到第J个村庄以内最中间的村庄上.

程序语言描述:

middle:=(a[i]+a[j]) div 2; ---|---|>FALSE

middle:=a[(i+j) div 2]; 　---|---|>TRUE

我就是因为这个始终ＤＰ不对，苦思冥想后终于想到这个错误！！！

在连续一段村里，放一个邮箱，放在那最好？放在中位点。

首先，不可能在这段村以外。（易证）

然后，第一个村到最后一个村分别到这个邮箱的距离之和永远是两村之距离的差。

第二个和倒数第二个村分别到这个邮箱的距离之和永远是两村之距离的差。。

。。

如果是偶数个村，那么放在中间两个村之间哪个地方都一样。

如果是奇数个，因为两端的村之和都一定了，所以放在中间那个村最好，距离为0。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

感谢大牛提供的方程~~~~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

动态方程看下几楼的就懂了

好好想，有好处的

f[i][j] 表示已经考虑了前i个邮局，其中第i个邮局放在第j个村庄所能取得的最小代价

则有 f[i][j] = min{f[k]+sum(mim(dis(r,k),dis(r,i)))}

O(N^4) 其实没有那么高 O(N^3)差不多

我是仅开n*m的二维数组就够了 O(n*m)