把方差公式先變形為?σ² = (1/n)∑xi²-x_a²

x_a為平均值。

由于要求標(biāo)準(zhǔn)差最小，只需方差最小，平均值都是一樣的，n也是一樣的，這樣原問題就變?yōu)榍筮@n快小棋盤總分的平方和最小

考慮左上角為（x1,y1）,右上角為（x2,y2）的棋盤，設(shè)該棋盤切割K次后得到的K+1塊矩形的總分平方和最小值為d[k,x1,y1,x2,y2]。該棋盤的總分平方和為

s[x1,y1,x2,y2].則它可以沿著橫線切，也可以沿著豎線切，然后選一塊繼續(xù)切（這里可以用遞歸完成）

狀態(tài)轉(zhuǎn)移方程為d[k,x1,y1,x2,y2] =? min{

min{ d[k-1,x1,y1,a,y2] + s[a+1,y1,x2,y2] , d[k-1,a+1,y1,x2,y2] + s[x1,y1,a,y2] },??? (x1 <= a < x2)

min{ d[k-1,x1,y1,x2,b] + s[x1,b+1,x2,y2] , d[k-1,x1,b+1,x2,y2] + s[x1,y1,x2,b] }? （y1 <= b < y2）

}

貼代碼：

View Code 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #define N 9 5 #define min(a,b) a<b?a:b 6 #define INF 100000000 7 int n; 8 int map[N][N]; 9 int presum[N][N]; 10 int d[16][N][N][N][N];//用d[k][x1][y1][x2][y2]表示左上角為（x1,y1） 11 //右下角為(x2,y2)的棋盤切成了k+1塊時最小的總分平方和值 12 void presolve() 13 { 14 //預(yù)處理，算出所有左上角為（1，1）的所有矩陣元素和 15 int i,j; 16 for(i=0; i<=N; ++i) 17 presum[0][i] = 0,presum[i][0] = 0; 18 for(i=1; i<N; ++i) 19 { 20 int rowsum = 0; 21 for(j=1; j<N; ++j) 22 { 23 scanf("%d",&map[i][j]); 24 rowsum += map[i][j]; 25 presum[i][j] = presum[i-1][j] + rowsum; 26 } 27 } 28 } 29 int rectSquare(int x1,int y1,int x2,int y2) 30 { 31 //計算左上角為(x1,y1),右下角為(x2,y2)的棋盤的總分平方和 32 int ret = presum[x2][y2] -presum[x1-1][y2] -presum[x2][y1-1] +presum[x1-1][y1-1]; 33 return ret*ret; 34 } 35 //DP程序 36 int DP(int k,int x1,int y1,int x2,int y2) 37 { 38 int t,c,e; 39 int MIN = INF;//用來求最后的d[k][x1][y1][x2][y2] 40 if(d[k][x1][y1][x2][y2] != -1)//記憶化搜索？？？已經(jīng)求過了，不再求，直接用 41 return d[k][x1][y1][x2][y2]; 42 if(k == 0)//切0刀，不就是該棋盤了嗎？最小值也是該棋盤的總分平方和，邊界條件 43 return d[k][x1][y1][x2][y2]=rectSquare(x1,y1,x2,y2); 44 for(int a = x1; a < x2; ++a) 45 { 46 //橫著切成了兩塊 47 c = rectSquare(a+1,y1,x2,y2); 48 e = rectSquare(x1,y1,a,y2); 49 t = min(DP(k-1,x1,y1,a,y2) + c,DP(k-1,a+1,y1,x2,y2) + e);//選取一塊繼續(xù)切割 50 MIN = min(MIN,t); 51 } 52 for(int b = y1; b < y2; ++b) 53 { 54 //豎著切成了兩塊 55 c = rectSquare(x1,b+1,x2,y2); 56 e = rectSquare(x1,y1,x2,b); 57 t= min(DP(k-1,x1,y1,x2,b)+c,DP(k-1,x1,b+1,x2,y2)+e);//選取一塊繼續(xù)切割 58 MIN = min(MIN,t); 59 } 60 d[k][x1][y1][x2][y2] = MIN;//所有的情況都考慮完后，所得就是該最小值 61 // printf("d[%d][%d][%d][%d][%d] = %d\n",k,x1,y1,x2,y2,d[k][x1][y1][x2][y2]); 62 return MIN; 63 } 64 int main() 65 { 66 // freopen("in.cpp","r",stdin); 67 scanf("%d",&n); 68 presolve(); 69 memset(d,-1,sizeof(d)); 70 int sumsquare = DP(n-1,1,1,8,8); 71 double f = n*sumsquare - presum[8][8]*presum[8][8]; 72 f = sqrt(f)/n; 73 printf("%.3f\n",f); 74 // printf("%d\n",0x7fffffff); 75 return 0; 76 } 注意：
用double，然后用%.3lf WA 用%.3fAC 在DP時min的初始值賦為10^7WA 賦為10^8AC 這點我還比較想得通，棋盤最大的總分和為6400，最大的平方和即為6400^6400,為40960000 你賦的min值至少應(yīng)該大于這個數(shù)，否則就不對了，所以10^7可能會錯 我中間賦過一個0x7fffffff，竟然導(dǎo)致出現(xiàn)了負數(shù)，怎么會啊。。。。。不了解
補充:我現(xiàn)在理解了為什么出現(xiàn)負數(shù)，因為0x7fffffff是最大的整數(shù)數(shù)了，再加就溢出了，成為負的了·····

轉(zhuǎn)載于:https://www.cnblogs.com/allh123/archive/2013/05/05/3061122.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的棋盘切割 DP POJ 1191的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。