$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：区间\ [x_1,y_1,x_2,y_2]\ 砍\ k\ \ 🔪\ 后的均方差$
  $属性：\min$

• $2. 状态转移$
  $横着切：min(dp(x1,y1,i,y2,k+1)+get(i+1,y1,x2,y2),dp(i+1,y1,x2,y2,k+1)+get(x1,y1,i,y2))$
  $竖着切：min(dp(x1,y1,x2,i,k+1)+get(x1,i+1,x2,y2),dp(x1,i+1,x2,y2,k+1)+get(x1,y1,x2,i))$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 9, M = 15;

int n,m=8;
int s[N][N];
double f[N][N][N][N][M];
double X;

//方差
double get(int x1,int y1,int x2,int y2)
{
    double sum=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]-X;
    return sum*sum/n;
}

double dp(int x1,int y1,int x2,int y2,int k)
{
    double &v=f[x1][y1][x2][y2][k];
    if(v>0) return v; //记忆化搜索，该块已计算过
    if(k==n) return get(x1,y1,x2,y2); //最后一块
    v=0x3f3f3f3f;

    //横着切
    for(int i=x1;i<x2;i++)
    {
        v=min(v,dp(x1,y1,i,y2,k+1)+get(i+1,y1,x2,y2));
        v=min(v,dp(i+1,y1,x2,y2,k+1)+get(x1,y1,i,y2));
    }

    //竖着切
    for(int i=y1;i<y2;i++)
    {
        v=min(v,dp(x1,y1,x2,i,k+1)+get(x1,i+1,x2,y2));
        v=min(v,dp(x1,i+1,x2,y2,k+1)+get(x1,y1,x2,i));
    }

    return v;
}

int main()
{
    cin>>n;

    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>s[i][j];
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; //二维前缀和
        }

    memset(f,-1,sizeof f);

    X=(double)s[m][m]/n; //平均值

    printf("%.3lf\n",sqrt(dp(1,1,8,8,1))); //均方差 = sqrt(方差)

    return 0;
}