欢迎来到天天文库
浏览记录
ID：43184149
大小：113.50 KB
页数：8页
时间：2019-10-01
《ACM试题1191 棋盘分割》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1191棋盘分割报告人：李鑫题意：将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共得到n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)题意：题意：每一次分割有以下4种方法：题意：原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。均方差xi为第i块矩形棋盘的总分其中分析：要求最小值。就是要求的最小值其中是定值后面就讨论求上面这个式子最小值的
2、问题分析：设x1x2…xk是把一个子棋盘进行k-1次分割依次得到k个的更小的子棋盘的过程中，每个小子棋盘上的总分值。当x1已经取定时，要使上式最小必须有最小。求(**)的问题跟求(*)的问题有相同的结构。解法：考虑动态规划的方法：设f(k,某个小棋盘)是把“某个小棋盘”分割成k块能得到的最小值，则有Thankyou!
此文档下载收益归作者所有
