HBC24199蓝魔法师,动态规划,树形dp[USACO 2019 Jan S]Icy Perimeter题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

Farmer John要开始他的冰激凌生意了！同时求得冰激凌球的面积和周长十分重要，因为Farmer John最终想要最小化周长与面积的比值，他称这是他的冰激凌的“冰周率”，当这个比率较小的时候，冰激凌化得比较慢，因为此时冰激凌单位质量的表面积较小。

Farmer John要开始他的冰激凌生意了！他制造了一台可以生产冰激凌球的机器，然而不幸的是形状不太规则，所以他现在希望优化一下这台机器，使其产出的冰激凌球的形状更加合理。 机器生产出的冰激凌的形状可以用一个N×N（1≤N≤1000）的矩形图案表示，例如： ##.... ....#. .#..#. .##### ...### ....## 每个'.'字符表示空的区域，每个'#'字符表示一块1×1的正方形格子大小的冰激凌。 不幸的是，机器当前工作得并不是很正常，可能会生产出多个互不相连的冰激凌球（上图中有两个）。一个冰激凌球是连通的，如果其中每个冰激凌的正方形格子都可以从这个冰激凌球中其他所有的冰激凌格子出发重复地前往东、南、西、北四个方向上相邻的冰激凌格子所到达。 Farmer John想要求出他的面积最大的冰激凌球的面积和周长。冰激凌球的面积就是这个冰激凌球中'#'的数量。如果有多个冰激凌球并列面积最大，他想要知道其中周长最小的冰激凌球的周长。在上图中，小的冰激凌球的面积为2，周长为6，大的冰激凌球的面积为13，周长为22。 注意一个冰激凌球可能在中间有“洞”（由冰激凌包围着的空的区域）。如果这样，洞的边界同样计入冰激凌球的周长。冰激凌球也可能出现在被其他冰激凌球包围的区域内，在这种情况下它们计为不同的冰激凌球。例如，以下这种情况包括一个面积为1的冰激凌球，被包围在一个面积为16的冰激凌球内： ##### #...# #.#.# #...# ##### 同时求得冰激凌球的面积和周长十分重要，因为Farmer John最终想要最小化周长与面积的比值，他称这是他的冰激凌的“冰周率”。当这个比率较小的时候，冰激凌化得比较慢，因为此时冰激凌单位质量的表面积较小。

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。

标签： HBC24199蓝魔法师 动态规划 树形dp[USACO 2019 Jan S]Icy Perimeter题解