思路
维护次数+上下左右的边界就行
C++ 代码
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define pii pair<int, int>
using namespace std;
const int maxn = 1e5+10;
template <typename _tp>
inline void read(_tp& x) {
char ch = getchar(), sgn = 0;
while (ch ^ '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') ch = getchar(), sgn = 1;
for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
if (sgn) x = -x;
}
int n;
double s = 0;
double g[10][10];
double pre[10][10];
double f[20][10][10][10][10];
double calc(int l, int r, int up, int down){
return pre[down][r] - pre[down][l-1] - pre[up-1][r] + pre[up-1][l-1];
}
double calc_(double x){
return (x-s)*(x-s);
}
double solve(int l, int r, int up, int down, int tim){
if(tim == n-1){
double tmp = calc(l, r, up, down);
return f[tim][l][r][up][down] = calc_(tmp);
}
if(f[tim][l][r][up][down] <= inf) return f[tim][l][r][up][down];
double res = inf;
//cout << l << " " << r << " " << up << " " << down << endl;
if(r - l >= 1){
for(int i = l; i < r; ++i){
res = min(res, solve(l, i, up, down, tim+1) + calc_(calc(i+1, r, up, down)));
res = min(res, solve(i+1, r, up, down, tim+1) + calc_(calc(l, i, up, down)));
}
}
if(down - up >= 1){
for(int i = up; i < down; ++i){
res = min(res, solve(l, r, up, i, tim+1) + calc_(calc(l, r, i+1, down)));
res = min(res, solve(l, r, i+1, down, tim+1) + calc_(calc(l, r, up, i)));
}
}
//cout << res << endl;
return f[tim][l][r][up][down] = res;
}
int main(){
read(n);
memset(f, 127, sizeof(f));
for(int i = 1; i <= 8; ++i){
for(int j = 1; j <= 8; ++j){
scanf("%lf", &g[i][j]);
s += g[i][j];
pre[i][j] = g[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
}
}
s /= 1.0*n;
double ans = solve(1, 8, 1, 8, 0);
printf("%.3lf", sqrt(ans/n*1.0));
return 0;
}
/*
3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3
*/