poj1191 바둑판 분할 동태 기획

마지막 물음에 대비해서 요 2주 동안 문제를 좀 더 만들어야겠다.오늘 저녁에 포제이의 문제를 하나 만들었는데 문제면은 8*8의 바둑판을 분할하여 분할된 각 블록 간의 균일한 방차를 최소화하도록 요구했다.바둑판은 여러 곳에서 서로 다른 블록에 대한 구화를 필요로 하기 때문에 바둑판을 예처리하여 (i, j)부터 (k, l)까지의 블록의 합을 계산하는 것이 필요하다.이 동시에 서로 다른 블록을 분할할 때 규모가 더욱 작은 하위 문제의 해답을 구하는 과정이 뚜렷하고 동태적인 계획을 채택하는 것을 고려할 수 있다.또한 문제면의 요구로 인해 분할된 두 블록을 동시에 재분할할 수 없기 때문에 귀속식의 문법에 주의해야 한다.또 수조가 크게 열릴 수도 있지만 당분간 피할 방법을 생각하지 못했다.개성 9*9*9*9*16의 적어도 나의 실현에서 비교적 이해하기 쉽겠지.

// chessboardParting.cpp:              。
//

#include "stdafx.h"
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAXN 16
int n;
int chessBoard[8][8];
int sum[9][9];
double dp[9][9][9][9][MAXN];//dp(u,v,x,y,k) means the maximum gotten from cutting from (u,v) to (x,y) for k times
double average;
double powe2(double a) { return a * a; }
double blockSum(int x1, int y1, int x2, int y2)
{
	return powe2(sum[x1][y1] - sum[x1][y2] - sum[x2][y1] + sum[x2][y2] - average);
}
void init()
{
	average = 0;
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++) {
			scanf("%d", &chessBoard[i][j]);
			average += chessBoard[i][j];
		}
	average /= n;
}
double minSeparation(int u, int v, int x, int y, int times)
{
	assert(u < x&&v < y&× >= 2);
	double ret = 6400001;
	for (int i = u + 1; i < x; i++)
		ret = min(ret, min(dp[u][v][i][y][1] + dp[i][v][x][y][times - 1],
			dp[u][v][i][y][times - 1] + dp[i][v][x][y][1]));
	for (int i = v + 1; i < y; i++)
		ret = min(ret, min(dp[u][v][x][i][1] + dp[u][i][x][y][times - 1],
			dp[u][v][x][i][times - 1] + dp[u][i][x][y][1]));
	return ret;
}
void solve()
{
	memset(sum, 0, sizeof(sum));
	for (int i = 7; i >= 0; i--) 
		for (int j = 7; j >= 0; j--) 
			sum[i][j] = chessBoard[i][j] + sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1];
	for (int i = 0; i < 9; i++)
		for (int j = 0; j < 9; j++)
			for (int k = 0; k < 9; k++)
				for (int l = 0; l < 9; l++)
					for (int times = 0; times <= n; times++)
						dp[i][j][k][l][times] = 6400001;
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			for (int k = i + 1; k < 9; k++)
				for (int l = j + 1; l < 9; l++) 
					dp[i][j][k][l][1] = blockSum(i, j, k, l);
	for (int partBlockNum = 2; partBlockNum < n; partBlockNum++) //part k times
		for (int i = 0; i < 8; i++) 
			for (int j = 0; j < 8; j++) 
				for (int k = i + 1; k < 9; k++) 
					for (int l = j + 1; l < 9; l++) 
						dp[i][j][k][l][partBlockNum] = minSeparation(i, j, k, l, partBlockNum);
	double ans = minSeparation(0, 0, 8, 8, n);
	printf("%.3lf
", sqrt(ans / n));
}
int main()
{
	while (scanf("%d", &n) != EOF) {
		init();
		solve();
	}
    return 0;
}