Contest-Petrozavodsk-Camp-2016-1

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[wiki:Contest_Information&&Solution go back]
== Summary ==

一套非常好的题目。题目质量很高，并且有一定的思维难度。

需要稳稳的把前中期打好。特别是算法显然的题目。

适合队伍中期（建队20场比赛以后）磨合和提升

== 题解 ==
'''Runespoor'''

* A : 

* F : 斯坦纳树 + 输出方案

* G ： 分割块数 = 挖去部分所有周围的点的联通块数（通过画图猜结论）

* J ：

* K ： 四边形不等式。要注意f[k][l][r]表示的至多k层的时候的最优答案，如果不足k层要最后转移
如果一开始就从f[k - 1][l][r]转移，会影响决策，因为这时的决策点未定义。

go back

Summary

一套非常好的题目。题目质量很高，并且有一定的思维难度。

需要稳稳的把前中期打好。特别是算法显然的题目。

适合队伍中期（建队20场比赛以后）磨合和提升

题解

Runespoor

• A :
• F : 斯坦纳树 + 输出方案
• G ： 分割块数 = 挖去部分所有周围的点的联通块数（通过画图猜结论）
• J ：
• K ： 四边形不等式。要注意f[k][l][r]表示的至多k层的时候的最优答案，如果不足k层要最后转移

如果一开始就从f[k - 1][l][r]转移，会影响决策，因为这时的决策点未定义。