狗家实习跪经

cherudim9 · 2017-11-15 12:46:19

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

cherudim9 · 2017-11-15 12:50:23

顺带一提。。。这个第二轮的第二题是可以做到O(nlogn)复杂度的，这是今年ACM World Final的D题。。Money for nothing

cherudim9 · 2017-11-15 12:51:14

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Corey_Lancer · 2017-11-15 12:58:48

LZ 第三轮给的input是什么呢？是给了村庄坐标，然后我们要自己放k个医院，使所有村庄到k个医院的路程和最小？

hychin · 2017-11-15 13:00:41

cherudim9 发表于 2017-11-15 12:46
第三题的参考解法（如果我没理解错题意的话）：

上来先对所有村庄进行排序，使得A(1)

题目如果是要求k个医院的最佳排放位置的话，确实应该是按照你说的这种DP做法，我以为是k个医院位置固定了，求最小distance总和。。

fireworkNo2 · 2017-11-15 22:32:10

bingbing_sakura 发表于 2017-11-15 12:36
lz第三题k个医院的坐标是给定的吗？还是要我们求能让距离和最小的k个医院坐标？

后者。村庄的坐标给定，然后需要选K个村庄来建造医院，使得所有村庄到医院的距离和最小。

fireworkNo2 · 2017-11-15 22:33:40

cherudim9 发表于 2017-11-15 12:46
第三题的参考解法（如果我没理解错题意的话）：

上来先对所有村庄进行排序，使得A(1)

看起来基本是正确的

fireworkNo2 · 2017-11-15 22:34:33

cherudim9 发表于 2017-11-15 12:50
顺带一提。。。这个第二轮的第二题是可以做到O(nlogn)复杂度的，这是今年ACM World Final的D题。。Money fo ...

是么？但是小哥当时只要求n^2。若有链接的话，愿闻其详

fireworkNo2 · 2017-11-15 22:34:57

cherudim9 发表于 2017-11-15 12:51
啊。。看错了，如果要求四个点的话不能这么做…………如果只要求两个点（对角）的话是O(nlogn)的

抱歉

没关系，谢谢补充！

570468837 · 2017-11-16 08:45:16

cherudim9 发表于 2017-11-15 12:46
第三题的参考解法（如果我没理解错题意的话）：

上来先对所有村庄进行排序，使得A(1)

这道题应该是建在k个不同的村庄吧。那层主在状态转移的时候怎么防止建在同一个村庄呢。
总之感觉这道题好绕。。