首页 > ACM题库 > HDU-杭电 > hdu 2517 棋盘分割-动态规划-[解题报告]C++
2014
02-09

hdu 2517 棋盘分割-动态规划-[解题报告]C++

棋盘分割

问题描述 :

将一个8*8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的部分继续如此分割,这样割了(n-1)次后,连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

原棋盘上每一格有一个分值,一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘,并使各矩形棋盘总分的均方差最小。
均方差

,其中平均值

xi为第i块矩形棋盘的总分。
请编程对给出的棋盘及n,求出O’的最小值。

输入:

第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

输出:

第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数,表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

样例输入:

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 3

样例输出:

1.633

题意:n刀切割棋盘

下面是8*8的棋盘,每个数字代表棋盘对应点的权值,问切割n刀后,每一块的和  的均方差最小是多少

均方差的公式需要先化简: 

由上式得,均方差最小 显然是要 Xi^2 最小

d[k][x1][y1][x2][y2]代表棋盘从(x1,y1)->(x2,y2)已经切了k刀 获得的最小的平方和

用sum[i][j] 代表 从(1,1)点 到 (i,j)点的权值和

这样答案就是 dp[n][1][1][8][8]/n  -(sum[8][8]/n)^2

用S[ (x1,y1) ,( x2,y2) ] 代表 这两点间的权值和

这里用递归dp

状态转移方程:

d[k][x1][y1][x2][y2]=

Min{  横向切: d[k-1] +剩下未切部分的平方和,纵向切:d[k-1]+剩下未切部分的平方和  }

横向切的最优解就是 Min{ d[ k-1,(x1,y1) , ( i ,y2) ] + S[ (i +1,y1) , ( x2 ,y2) ] ,  d[ k-1,(i+1,y1) , ( x2 ,y2) ] + S[ (x1,y1) , ( i ,y2) ] }  ( x1<= i <x2)

上面的意思就是: 在x=i处切一刀的最优解 

同理可以容易推出纵向切法的dp方程

#include<stdio.h>
#include<math.h>
#include <string.h>
#define INF 1<<29
int map[9][9],sum[9][9];
int d[15][9][9][9][9];
inline int Min(int a,int b){return a>b?b:a;}

int s(int x1,int y1,int x2,int y2){
	int temp=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]; return temp*temp;
}

int dp(int k,int x1,int y1,int x2,int y2){
	if(d[k][x1][y1][x2][y2]!=-1)return d[k][x1][y1][x2][y2];
	if(k==1)return s(x1,y1,x2,y2);
	int ans=INF,i;
	for(i=x1;i<x2;i++)
	{
		ans=Min(dp(k-1,x1,y1,i,y2)+s(i+1,y1,x2,y2),ans);
		ans=Min(dp(k-1,i+1,y1,x2,y2)+s(x1,y1,i,y2),ans);
	}
	for(i=y1;i<y2;i++)
	{
		ans=Min(dp(k-1,x1,y1,x2,i)+s(x1,i+1,x2,y2),ans);
		ans=Min(dp(k-1,x1,i+1,x2,y2)+s(x1,y1,x2,i),ans);
	}

	return d[k][x1][y1][x2][y2]=ans;
}
int main()
{
	int n,i,j,k;
	while(~scanf("%d",&n)){
		memset(map,0,sizeof(map));
		for(i=1;i<=8;i++)
			for(j=1;j<=8;j++)
				scanf("%d",&map[i][j]);

		memset(sum,0,sizeof(sum));
		for(i=1;i<=8;i++)  
			for(j=1;j<=8;j++)   
				sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+map[i][j];  //得到sum数组

			memset(d,-1,sizeof(d));
		
			int ans=dp(n,1,1,8,8);
			double aver=(double)sum[8][8]/(double)n;
			double last=sqrt((double)ans/(double)n-aver*aver);
			printf("%.3lf\n",last);
	}
	return 0;
}

解题转自:http://blog.csdn.net/acmmmm/article/details/9731129