Problem E. Tenzing and Triangle 只要能写出暴力 dp 就成功了 90% 啦！ 不妨先把所有点都加起来，考虑最优能通过覆盖节省多少。我们发现一个有用的性质是，三角形覆盖的区域，是不需要重叠的，因此似乎可以简单的 1D/1D 动态规划。 这里我们用树状数组，可以维护出三角形覆盖区域的代价。 #include #include using namespace lastwe…
Problem E. Tenzing and Triangle 只要能写出暴力 dp 就成功了 90% 啦！ 不妨先把所有点都加起来，考虑最优能通过覆盖节省多少。我们发现一个有用的性质是，三角形覆盖的区域，是不需要重叠的，因此似乎可以简单的 1D/1D 动态规划。 这里我们用树状数组，可以维护出三角形覆盖区域的代价。 #include #include using namespace lastwe…
讨论
登录后参与讨论
还没有评论，来说第一句吧。