解题思路

算法设计

采用动态规划方法解决棋盘分割问题，通过最小化各块分值平方和来达到最小化方差的目的。

核心思想

• 方差最小化转化为分值平方和最小化
• 利用动态规划递推求解最优分割方案

状态定义

状态转移方程

dp[k][x1][y1][x2][y2] = min{
    // 垂直分割
    min{
        dp[0][x1][y1][t][y2] + dp[k-1][t+1][y1][x2][y2] | x1 ≤ t < x2
        dp[k-1][x1][y1][t][y2] + dp[0][t+1][y1][x2][y2] | x1 ≤ t < x2
    },
    // 水平分割
    min{
        dp[0][x1][y1][x2][t] + dp[k-1][x1][t+1][x2][y2] | y1 ≤ t < y2
        dp[k-1][x1][y1][x2][t] + dp[0][x1][t+1][x2][y2] | y1 ≤ t < y2
    }
}

实现步骤

1. 预处理计算所有不分割区域的平方值(dp[0])
2. 从k=1开始逐步计算k次分割的最优解
3. 对于每个k值，枚举所有可能的区域和分割方式
4. 记录最小值作为当前状态的最优解

复杂度分析

• 时间复杂度：O(k*n^4)，其中n为棋盘边长
• 空间复杂度：O(k*n^4)，需要存储动态规划表

优化建议

• 使用记忆化搜索减少不必要的计算
• 预处理区域和数组加速分值计算
• 考虑对称性减少状态数量

#include<iostream>
#include<map>
#include<string>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<memory.h>
using namespace std;
int dp[15][15][15][15][15];//动态规划数组，记录状态
int m[10][10];
int sum[15][15] = { 0 };//从左上角（1，1）到（i，j）的棋盘的权值之和及sum[i][j]
int Sum = 0;
int n;
int calsum(int x1, int y1, int x2, int y2)//计算从（x1，y1）到（x2，y2）的棋盘的权值之和
{
    return (sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);
}
int solve(int n, int x1, int y1, int x2, int y2)//递归函数，n表示当前部分还能分割成多少块，x1,y1,x2,y2分别表示当前棋盘左上角和右下角的坐标
{
    //该函数返回剩余分割成n块的从（x1,y1）到（x2,y2）的棋盘内部n块被分割棋盘的方差的平方和的最小值
    int t, a, b, c, e;
    int ma = 1e7;
    int& ans = dp[n][x1][y1][x2][y2];//注意这里ans用引用形式，ans改变时，相应的dp值也发生改变
    if (ans != -1)//ans非负表示dp值已经记录，可以直接引用，节省时间
    {
        return ans;
    }
    if (n == 1)//n=1时，达到边界条件
    {
        t = calsum(x1, y1, x2, y2);
        ans = t * t;
        return ans;
    }
    for (a = x1; a < x2; a++)//从x方向进行分割
    {
        c = calsum(a + 1, y1, x2, y2);
        e = calsum(x1, y1, a, y2);
        t = min(c*c + solve(n - 1, x1, y1, a, y2), e*e + solve(n - 1, a + 1, y1, x2, y2));//从分别对左右侧进行接下来的分割中选择最小值
        if (ma > t)
        {
            ma = t;
        }
    }
    for (b = y1; b < y2; b++)//同上，不过这次是从y方向进行分割
    {
        c = calsum(x1, b + 1, x2, y2);
        e = calsum(x1, y1, x2, b);
        t = min(c*c + solve(n - 1, x1, y1, x2, b), e*e + solve(n - 1, x1, b + 1, x2, y2));
        if (ma > t)
        {
            ma = t;
        }
    }
    ans = ma;
    return ma;
}
int main()
{
    memset(dp, -1, sizeof(dp));//一开始全部赋成-1
    cin >> n;
    for (int i = 1; i <= 8; i++)
    {
        Sum = 0;//Sum记录棋盘每一行的权值
        for (int j = 1; j <= 8; j++)
        {
            cin >> m[i][j];
            Sum += m[i][j];
            sum[i][j] += sum[i - 1][j] + Sum;
        }
    }
    double result = n * solve(n, 1, 1, 8, 8) - sum[8][8] * sum[8][8];
    cout << setiosflags(ios::fixed) << setprecision(3) << sqrt(result / (n*n)) << endl;//按照公式计算
    return 0;
}