題目描述

將一個(gè)8*8的棋盤(pán)進(jìn)行如下分割：將原棋盤(pán)割下一塊矩形棋盤(pán)并使剩下部分也是矩形，再將剩下的部分繼續(xù)如此分割，這樣割了n-1次后，連同最后剩下的矩形棋盤(pán)共有n塊矩形棋盤(pán)。 (每次切割都只能沿著棋盤(pán)格子的邊進(jìn)行)

原棋盤(pán)上每一格有一個(gè)分值，一塊矩形棋盤(pán)的總分為其所含各格分值之和。現(xiàn)在需要把棋盤(pán)按上述規(guī)則分割成n塊矩形棋盤(pán)，并使各矩形棋盤(pán)總分的均方差最小。求出均方差的最小值。
其中，均方差的定義為：

（里面的括號(hào)應(yīng)該還有一個(gè)平方，不然固輸0豈不美哉）

數(shù)據(jù)范圍

1<n<15，所有數(shù)均為不大于100的非負(fù)整數(shù)

解析

分析題面可以發(fā)現(xiàn)一些結(jié)論：
1.只要大矩陣與n確定，平均值就是可以算出的定值
2.每次分完后只能對(duì)其中的一部分繼續(xù)切割
對(duì)于第2條舉個(gè)例子：n=4時(shí)，田字型的切割就是不合法的，這對(duì)于本題至關(guān)重要
我們可以先算出均方差根號(hào)里面那個(gè)西格瑪加和的總值的最小值，最后再除n開(kāi)根號(hào)
定義dp[x1][y1][x2][y2][k]:左上角為x1,y1,右下角為x2,y2還可以切k刀時(shí)，切成的k+1部分西格瑪方差的最小值
顯然，k=0時(shí)：

if(k==0) return abs((double)he(x1,y1,x2,y2)-ave)*abs((double)he(x1,y1,x2,y2)-ave);

ave為提前可算好的平均值，he函數(shù)可以用二維前綴和O（1）求出，具體見(jiàn)代碼（其實(shí)遍歷求本題時(shí)間可能也爆不了。。。 ）
對(duì)于轉(zhuǎn)移，我們枚舉切出去的那個(gè)不能再切的矩形的位置即可

代碼

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <string> #include <queue> #include <string> #include<map> #define ll long long #define mem(a,b) memset(a,b,sizeof(a)); #define ull unsigned ll using namespace std; const int N=15; int m,n,tot; int mp[10][10],sum[10][10]; double ave; double dp[N][N][N][N][N]; int he(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]; } double find(int x1,int y1,int x2,int y2,int k){if(dp[x1][y1][x2][y2][k]) return dp[x1][y1][x2][y2][k];if(k==0) return abs((double)he(x1,y1,x2,y2)-ave)*abs((double)he(x1,y1,x2,y2)-ave);dp[x1][y1][x2][y2][k]=1e9;for(int i=x1;i<x2;i++){//橫著切 dp[x1][y1][x2][y2][k]=min(dp[x1][y1][x2][y2][k],find(x1,y1,i,y2,0)+find(i+1,y1,x2,y2,k-1));dp[x1][y1][x2][y2][k]=min(dp[x1][y1][x2][y2][k],find(x1,y1,i,y2,k-1)+find(i+1,y1,x2,y2,0));//注意這里還要反著枚舉一遍，因?yàn)椴荒芮械牟糠挚赡茉谙逻?}for(int j=y1;j<y2;j++){//豎著切 dp[x1][y1][x2][y2][k]=min(dp[x1][y1][x2][y2][k],find(x1,y1,x2,j,0)+find(x1,j+1,x2,y2,k-1));dp[x1][y1][x2][y2][k]=min(dp[x1][y1][x2][y2][k],find(x1,y1,x2,j,k-1)+find(x1,j+1,x2,y2,0));}return dp[x1][y1][x2][y2][k]; } int main(){scanf("%d",&n);for(int i=1;i<=8;i++){for(int j=1;j<=8;j++) scanf("%d",&mp[i][j]);}for(int i=1;i<=8;i++){for(int j=1;j<=8;j++) sum[i][j]=sum[i][j-1]+mp[i][j];}for(int j=1;j<=8;j++){for(int i=1;i<=8;i++) sum[i][j]+=sum[i-1][j];}ave=1.0*sum[8][8]/n;printf("%.3lf",sqrt(1.0*find(1,1,8,8,n-1)/n)); } /* 樣例： 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 3ans:1.633 */

心得

一次AC萬(wàn)歲！！！！

這道dp做的還是不錯(cuò)的，尤其是很快發(fā)現(xiàn)了解析中提到的兩條關(guān)鍵結(jié)論，從而帶出了思路
所以要仔細(xì)審題！！
dp就像數(shù)學(xué)平幾，有時(shí)候思路一下子通了就不難了awa

thanks for reading!

總結(jié)

以上是生活随笔為你收集整理的不止代码：ybtoj-棋盘分割（二维区间dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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