題目鏈接：http://poj.org/problem?id=1191
題意：中文題誒～
思路：這道題有幾個關鍵點需要想通，不然會比較難做．．．
首先，題目給出的標準差公式並不是很好計算，需要給它變下形：
ans = sqrt(sum(xi-x)^2/n) (其中x爲平均面積，xi爲某個矩形面積．．．
ans^2 = sum(xi-x)^2/n
= sum(xi^2)/n - sum(2*xi*x)/n - sum(x^2)/n
=sum(xi^2)/n - 2x*sum(xi)/n - n*x^2/n
= sum(xi^2)/n - 2x*nx/n - x^2
= sum(xi^2)/n - x^2
顯然 sum(xi^2)/n >= x^2，所以只要求得 min(sum(xi^2)/n) 即求得 min(sum(xi^2)) 即可；
对于求 min(sum(xi^2)) 显然可以用dfs解决(据说还可以dp), 不过这里的 i <15，太暴力会tle，需要加个记忆优化；
注意：由一对顶点可以确定一个矩形；
题目要求只能对分割后得到的两个矩形其中一个继续分割；
可以先对矩形预处理一下，sum(x, y) = sum(x-1, y) + sum(x, y-1) + value - sum(x-1, y-1)，这样再计算单个矩形面积时会方便一些；
代码：
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 using namespace std; 6 7 const int MAXN=10; 8 const int inf=1e9; 9 int a[MAXN][MAXN], n; 10 int dp[MAXN][MAXN][MAXN][MAXN][MAXN+5]; 11 12 int area(int x1, int y1, int x2, int y2){ 13 return a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]; 14 } 15 16 int dfs(int x1, int y1, int x2, int y2, int cnt){ 17 if(dp[x1][y1][x2][y2][cnt]!=-1) return dp[x1][y1][x2][y2][cnt]; 18 if(cnt==n){ 19 int gg=area(x1, y1, x2, y2); 20 return dp[x1][y1][x2][y2][cnt]=gg*gg; 21 } 22 int m=inf; 23 for(int i=x1; i<x2; i++){//注意这里是从x1开始，因为可以选择不切割 24 int l=area(x1, y1, i, y2); 25 int r=area(i+1, y1, x2, y2); 26 m=min(m, min(dfs(x1, y1, i, y2, cnt+1)+r*r, dfs(i+1, y1, x2, y2, cnt+1)+l*l)); 27 } 28 for(int i=y1; i<y2; i++){//同理，这里是从y1开始 29 int l=area(x1, y1, x2, i); 30 int r=area(x1, i+1, x2, y2); 31 m=min(m, min(dfs(x1, y1, x2, i, cnt+1)+r*r, dfs(x1, i+1, x2, y2, cnt+1)+l*l)); 32 } 33 return dp[x1][y1][x2][y2][cnt]=m; 34 } 35 36 int main(void){ 37 while(cin >> n){ 38 memset(a, 0, sizeof(a)); 39 memset(dp, -1, sizeof(dp)); 40 for(int i=1; i<=8; i++){ 41 for(int j=1; j<=8; j++){ 42 int x; 43 cin >> x; 44 a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+x; 45 } 46 } 47 double avi=a[8][8]*1.0/n; 48 double cnt=dfs(1, 1, 8, 8, 1)*1.0/n; 49 printf("%.3lf ", sqrt(cnt-avi*avi)); 50 } 51 return 0; 52 }