题目大意：

有一个8*8的正方形棋盘，每个格子有相对应的值，对于这个棋盘，我们可以割（n-1）次，使得切割后的n块棋盘权值和的标准差最小。

同时每次切割后下一次切割只能对上次被切割的其中一块进行切割，另一块就不能够再被切割了。

思路：

dp

首先可以注意到棋盘非常小，是8*8，n<15也并不大，先利用方差来计算，最后在用标准差

dp(x1,y1,x2,y2,k)表示(x1,y1) 为左上角(x2,y2)为右下角的矩形切k刀的答案。

首先，我们可以把方差的公式化简一下：

   1/n(x1^2+x2^2+...+xn^2-2*x1*avg-2*x2*avg-...-2*xn*avg+n*avg*avg)

=1/n(x1^2+x2^2+...+xn^2-2*avg*sum+sum*avg)

=1/n(x1^2+x2^2+...+xn^2-n*avg*avg)

=(x1^2+x2^2+...+xn^2)/n-avg^2

因为所有矩阵的和一定，所以我们先预处理出avg，然后dp表示每块的答案就好了

先预处理每块不切的情况 即dp(x1,y1,x2,y2,0)=sum^2

然后最外圈套k

枚举每一块的切割线以及左右两边哪边是新切的

最后把dp(0,0,7,7,n-1)带入公式

就做完了哈哈哈

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #define long long ll11 #define inf 21474836412 using namespace std;13 int n,map[9][9],sum[9][9];14 int f[9][9][9][9][17];15 double avg;16 int main()17 {18 scanf("%d",&n);19 for(int i=0;i<8;i++)20 for(int j=0;j<8;j++)21 {22 scanf("%d",&map[i][j]);23 sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+map[i][j];24 avg+=map[i][j];25 }26 avg=1.0*avg/n;27 for(int i1=0;i1<8;i1++)28 for(int j1=0;j1<8;j1++)29 for(int i2=i1;i2<8;i2++)30 for(int j2=j1;j2<8;j2++)31 {32 int s=sum[i2][j2]-sum[i1-1][j2]-sum[i2][j1-1]+sum[i1-1][j1-1];33 f[i1][j1][i2][j2][0]=s*s;34 }35 for(int k=1;k