题意：
思路：不知道直接暴力枚举所有情况行不行。。。
我们可以把答案转化为
所以答案就是求xi2的最小值，那么我们可以直接用区间DP来写。设dp[x1][y1][x2][y2][k]为x1 y1 到 x2 y2 区间分割为k份的最下平方和，显然k = 1是就是区间和的平方。
写了6层for，写出来自己都不信。。。
交C++才过。。。
代码：
#include#include #include #include #include #include #include using namespace std;typedef long long ll;const int maxn = 10 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1000000007;int n;double w[maxn][maxn], dp[maxn][maxn][maxn][maxn][maxn], sum[maxn][maxn];double get(int x1, int y1, int x2, int y2){ return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];}int main(){ scanf("%d", &n); memset(sum, 0, sizeof(sum)); for(int i = 1; i <= 8; i++){ for(int j = 1; j <= 8; j++){ scanf("%lf", &w[i][j]); sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + w[i][j]; } } double per = sum[8][8] / n; for(int x1 = 1; x1 <= 8; x1++){ for(int y1 = 1; y1 <= 8; y1++){ for(int x2 = x1; x2 <= 8; x2++){ for(int y2 = y1; y2 <= 8; y2++){ double ret = get(x1, y1, x2, y2); dp[x1][y1][x2][y2][1] = ret * ret; } } } } for(int k = 2; k <= n; k++){ for(int x1 = 1; x1 <= 8; x1++){ for(int y1 = 1; y1 <= 8; y1++){ for(int x2 = x1; x2 <= 8; x2++){ for(int y2 = y1; y2 <= 8; y2++){ dp[x1][y1][x2][y2][k] = INF; for(int t = x1; t < x2; t++){ dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k], dp[x1][y1][t][y2][1] + dp[t + 1][y1][x2][y2][k - 1]); dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k], dp[x1][y1][t][y2][k - 1] + dp[t + 1][y1][x2][y2][1]); } for(int t = y1; t < y2; t++){ dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k], dp[x1][y1][x2][t][1] + dp[x1][t + 1][x2][y2][k - 1]); dp[x1][y1][x2][y2][k] = min(dp[x1][y1][x2][y2][k], dp[x1][y1][x2][t][k - 1] + dp[x1][t + 1][x2][y2][1]); } } } } } } printf("%.3lf\n", sqrt(dp[1][1][8][8][n] / n - per * per)); return 0;}