`
holoblog
  • 浏览: 1217577 次
博客专栏
E0fcf0b7-6756-3051-9a54-90b4324c9940
SQL Server 20...
浏览量:18781
文章分类
社区版块
存档分类
最新评论

棋盘分割 动态规划 poj 1191

 
阅读更多

题目连接:http://poj.org/problem?id=1191

题目大意:讲一个8*8的棋盘进行分割:将原棋盘割下一块矩形棋盘并保证剩下的棋盘也是矩形,再将剩下的部分继续如此分割,这样割了n-1次后,连通最后剩下的棋盘共有n块矩形棋盘。每次切割都沿着棋盘格子的边进行。棋盘上每一格子都有一个分值,一块矩形棋盘的总分为其所含各个格子分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。

给出棋盘及n,求最小的均方差。

题目分析:根据均方差的定义可以将其展开,从而得到均方差其实最终等于各块平方和-均值的平方然后再开平方。这个很容易推倒,由于数学公式不好打,所以具体过程就不写了,很容易推得。所以次问题就转化为求各块平方和的最小值,即找一种切割方式使得各块分值和的均方差最小即可。

说白了这个题就是枚举各种切割方法,然后累计切割次数即可。

代码如下:



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics