前缀和预处理,老题就不多说算法了,均方差可以转换一下计算公式,方便计算,直接看代码就行了。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 16,n = 8;
int a[N][N];
double sum[N][N];
double f[N][N][N][N][N];
int m;
int main()
{
cin >> m;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
cin >> a[i][j] , sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
for(int x1 = 1 ; x1 <= n ; x1++)
for(int y1 = 1 ; y1 <= n ; y1++)
for(int x2 = x1; x2 <= n ; x2++)
for(int y2 = y1 ; y2 <= n ; y2++)
f[0][x1][y1][x2][y2] = (sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]) * (sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]);
for(int i = 1 ; i < m ; i++)
for(int x1 = 1 ; x1 <= n ; x1++)
for(int y1 = 1 ; y1 <= n ;y1++)
for(int x2 = x1 ; x2 <= n ;x2++)
for(int y2 = y1 ; y2 <= n ; y2++)
{
double minn = 0x7f7f7f7f;
for(int j = x1 ; j < x2 ; j++)
minn = min(minn , min(f[i-1][x1][y1][j][y2]+f[0][j+1][y1][x2][y2],f[0][x1][y1][j][y2]+f[i-1][j+1][y1][x2][y2]));
for(int k = y1 ; k < y2 ; k++)
minn = min(minn , min(f[i-1][x1][y1][x2][k]+f[0][x1][k+1][x2][y2],f[0][x1][y1][x2][k]+f[i-1][x1][k+1][x2][y2]));
f[i][x1][y1][x2][y2] = minn;
}
double adv = double(sum[n][n]/m);
double ans = sqrt(f[m-1][1][1][n][n]/m-adv*adv);
printf("%.3lf",ans);
return 0;
}
用的y总开始讲的那个公式的变形!!谢谢!!!