棋盘分割 将一个8*8的棋盘进行如下分割:
将原棋盘割下一块矩形棋盘并使剩下部分也是矩形, 再将剩下的部分继续如此分割, 这样割了(n-1)次后, 连同最后剩下的矩形棋盘共有n块矩形棋盘. (每次切割都只能沿着棋盘格子的边进行)。
原棋盘上每一格有一个分值, 一块矩形棋盘的总分为其所含各格分值之和 现在需要把棋盘按上述规则分割成 n 块矩形棋盘, 并使各矩形棋盘总分的均方差最小。
xi 为第 i 块矩形棋盘的总分 请编程对给出的棋盘及 n, 求出 σ 的最小值 2 1 n i i n x x 1 n i i x x n 3 输入 第1行为一个整数n (1 < n < 15) 第2行至第9行每行为8个小于100的非负整数, 表示棋盘上 相应格子的分值 每行相邻两数之间用一个空格分隔 输出 仅一个数, 为σ (四舍五入精确到小数点后三位)
问题分析 (1) 每一次分割有以下4种方法:
问题分析 (2)
问题分析 (3)
只想到这个还不够, TLE! 对于某个fun(n,x1,y1,x2,y2)来说, 可能使用多次这个值, 所以每次 都计算太消耗时间 解决办法: 记录表
用res[n][x1][y1][x2][y2]来记录fun(n,x1,y1,x2,y2)
res初始值统一为-1
当需要使用fun(n,x1,y1,x2,y2)时, 查看res[n][x1][y1][x2][y2]
如果为-1, 那么计算fun(n,x1,y1,x2,y2), 并保存于 res[n][x1][y1][x2][y2]
如果不为-1, 直接返回res[n][x1][y1][x2][y2]
参考程序
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.