首页 > 代码库 > 初学DP（2） 黑书中的《棋盘分割》
初学DP（2） 黑书中的《棋盘分割》
题意：
将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差
，其中平均值
，xi为第i块矩形棋盘的总分。
请编程对给出的棋盘及n，求出O‘的最小值。
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差
，其中平均值，xi为第i块矩形棋盘的总分。 请编程对给出的棋盘及n，求出O‘的最小值。
分析：
将公式化简可以得到σ2 = 1/n*∑xi2 - ˉx，也就是只需要使∑xi2最小即可；
我们用dp[a][i][j][k][s]表示第a次切割（i，j，k，s）棋盘的最小值；
则有
minmin=min(minmin,min(dp[a-1][i][j][m][s]+t*t,dp[a-1][m+1][j][k][s]+t2*t2)); (i<=m<k)
minmin=min(minmin,min(dp[a-1][i][j][k][m]+t*t,dp[a-1][i][m+1][k][s]+t2*t2)); (j<=m<s)
dp[a][i][j][k][s]=minmin;poj1191 ：http://poj.org/problem?id=1191
参考代码：
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
#define inf 0xffffff
int n,a[10][10],sum[10][10];
int dp[15][10][10][10][10];
int countsum(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 fun(int k){
//初始化
for (int i=0;i<8;i++)
for (int j=0;j<8;j++)
for (int k=0;k<8;k++)
for (int s=0;s<8;s++){
int t=countsum(i,j,k,s);
dp[0][i][j][k][s]=t*t;
}
for (int a=1;a<=k;a++){
for (int i=0;i<8;i++){
for (int j=0;j<8;j++){
for (int k=0;k<8;k++){
for (int s=0;s<8;s++){
int minmin = inf;
if ((k-i+1)*(s-j+1)<a+1){
dp[a][i][j][k][s]=minmin;
continue;
}
for (int m=i;m<k;m++){
int t=countsum(m+1,j,k,s);
int t2=countsum(i,j,m,s);
minmin=min(minmin,min(dp[a-1][i][j][m][s]+t*t,dp[a-1][m+1][j][k][s]+t2*t2));
}
for (int m=j;m<s;m++){
int t=countsum(i,m+1,k,s);
int t2=countsum(i,j,k,m);
minmin=min(minmin,min(dp[a-1][i][j][k][m]+t*t,dp[a-1][i][m+1][k][s]+t2*t2));
}
dp[a][i][j][k][s]=minmin;
}
}
}
}
}
return dp[k][0][0][7][7];
}
int main(){
while (cin>>n){
for (int i=0;i<8;i++){
int s=0;
for (int j=0;j<8;j++){
cin>>a[i][j];
s+=a[i][j];
if (i==0)
sum[i][j]=s;
else
sum[i][j]=sum[i-1][j]+s;
}
}
double ans = n*fun(n-1)-sum[7][7]*sum[7][7];
cout<<fixed<<setprecision(3)<<sqrt(ans/(n*n))<<endl;
}
return 0;
}用C++提交答案是WA 用G++就AC了。。。初学DP（2） 黑书中的《棋盘分割》
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。