再次ＡＣ一个莫名其妙的题目．．．

　为什么取中位数就是最优值．．还是不懂

此题可以归为经典的线性DP

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

vijos的速度真是快

本机速度最慢的一个点300ms...(C375..)

本题是一道动态规划问题。将n个村庄按坐标递增依次编号为1，2，……，n，各个邮局的坐标为d[1..n]，状态表示描述为：m表示在前j个村庄建立i个邮局的最小距离和。所以，m[p,n]即为问题的解，且状态转移方程和边界条件为：

m[1,j]=w[1,j];

m=max{m+w[k+1,j]}; (i≤j, i≤k≤j-1)

其中w表示在d之间建立一个邮局的最小距离和，可以证明，当仅建立一个邮局时，最优解出现在中位数，即设建立邮局的村庄为k，则 ，于是，我们有：

　　w=w+|d[k]-d[i]| (1

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

有点悬！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

神牛可能有O(n^2)的算法，普通人就用O(n^3)的吧,预处理O(n*n).

主转移方程:

用f表示在前j个村庄建i个邮局所可达到的最小代价.

f:=min{f+g[k+1,j-k]|i-1

最先整了个O(n^5)的程序！严重超时

经过预处理,降到了O(n^3+n^2)

F表示前i个村庄由j个邮局控制的最小代价

方程:

f=min{f[k,j-1]+p[k+1,i-k]|j-1

编译通过...

├ 测试数据 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

郁闷ing。。。。。

而且差了好远。。。

编译通过...

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

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

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

├ 测试数据 04：答案错误...　├ 标准行输出 18394

　├ 错误行输出 3292

├ 测试数据 05：答案错误...　├ 标准行输出 24780

　├ 错误行输出 2266

├ 测试数据 06：答案错误...　├ 标准行输出 18153

　├ 错误行输出 1965

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

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

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

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

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

Unaccepted 有效得分：70 有效耗时：119ms

看了wangsc的程序

和我的一比

我才发现

什么叫

差距

天！！

牛的程序就是不一样

谁能给一个O(p*n)的 经过四边形不等式优化的算法的题解？

毛子青大牛的论文看不懂……

w:=w+|d[(i+j) div 2]-d[k]|(1

谢谢帮助，，，做了好久，最短距离一直不会求。

wangsc啊,这个题目难道不该是3啊...

(Invalid img)

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

想求i到J之间放一个邮局的最优方法 是将邮局放在（I+J）DIV 2 +1 处

那个程序是 magic cui写滴……连变量名都没改

就光把最前面“program energy”去掉了……

凸-_-凸

王啊！你只不知道这里不能发答案啊！