二刷提高课，题解目录在这里— 提高课的题解目录

像这种问我们如何切分使得最后结果最小，但是我们无法确定每一步该如何切
所以这里应该用爆搜的模式，但是爆搜肯定不行，所以我们使用DP来进行记录来优化
但是这里当我们枚举所有的起点终点时，还要去枚举横切竖切，需要五六个for循环
所以这里可以使用记忆化搜索，何谓记忆化搜索？
当我们使用for循环遍历时我们将每个答案都记录了下来（使用的f[i][j]数组）
而记忆化搜索只会将这一层的答案先写出来
也就是说for遍历答案是从小到大出来的
记忆化搜索是 从小到对应的大，再从小到对应的大.....
记忆化搜索可以认为是使用递归来实现for循环的功能
注意这里使用的状态转移记录f[N][N][M][M][K]（遇到类似矩阵也可以这样写）

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=15,M=9;
int s[M][M];
int n,m=8;
double f[M][M][M][M][N];
double x;
double get(int x1,int y1,int x2,int y2)
{
    double sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]-x;
    return (double)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==1)return v=get(x1,y1,x2,y2);
    v=1e9+0.1;
    for(int i=x1;i<x2;i++)
    {
        v=min(v,dp(i+1,y1,x2,y2,k-1)+get(x1,y1,i,y2));
        v=min(v,dp(x1,y1,i,y2,k-1)+get(i+1,y1,x2,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];
        }
    }
    x=(double)s[m][m]/n;
    //我们需要判断是否切过了，因为会存在切的结果相同的情况
    memset(f,-1,sizeof f);//不是-1是一个负数
    printf("%.3lf",sqrt(dp(1,1,8,8,n)));
    return 0;
}