题意

https://www.luogu.com.cn/problem/P5752
将8*8矩阵切割为 n (n<15) 块，求各块价值方差的最小值

分析

关键词：方差——方差与 “平均数” 和 “平方之和” 有关
突破口：平均数是定值，只需最小化“平方之和”即可

由于是矩阵，考虑二维区间dp；
切割为n块，考虑将切割为几块设为子问题；
特殊的切割方法，每一个子问题必然有一个接下来没有被切割的“大块”，考虑利用这一块为“不可拆分极大块”进行决策转移；
f [ t ] [ x ] [ y ] [ xx ] [ yy ] 表示切为 t 块，( i , j ) 到 ( k , l ) 的 平方之和 的最小值。

注意：决策时要枚举四个方向，不能只枚举左和上

代码

f[1][x][y][xx][yy] = get_sum(x, y, xx, yy) * get_sum(x, y, xx, yy);

for(int t = 2; t <= n; t++)
  for(int x_len = 1; x_len <= 8; x_len++)
    for(int y_len = 1; y_len <= 8; y_len++)
      for(int x = 1; x <= 8 - x_len + 1; x++)
	for(int y = 1; y <= 8 - y_len + 1; y++)
	{
	  LL xx = x + x_len - 1;
	  LL yy = y + y_len - 1;
	  for(int k = x; k < xx; k++)
	  {
	    f[t][x][y][xx][yy] = min(f[t][x][y][xx][yy], f[1][x][y][k][yy] + f[t - 1][k + 1][y][xx][yy]);
            //only consider left or up is first block, but in fact left_up may be a small block
	    f[t][x][y][xx][yy] = min(f[t][x][y][xx][yy], f[t - 1][x][y][k][yy] + f[1][k + 1][y][xx][yy]);
	    }	
	    for(int k = y; k < yy; k++)
	    {
	      f[t][x][y][xx][yy] = min(f[t][x][y][xx][yy], f[1][x][y][xx][k] + f[t - 1][x][k + 1][xx][yy]);
	      f[t][x][y][xx][yy] = min(f[t][x][y][xx][yy], f[t - 1][x][y][xx][k] + f[1][x][k + 1][xx][yy]);
	    }// the first bolck may be 4 direction : left up right down
	}