Poj 1191 바둑판 분할

제목: 8 * 8 의 바둑판 을 다음 과 같이 나 눕 니 다. 원래 의 바둑판 을 사각형 바둑판 하 나 를 자 르 고 나머지 부분 도 사각형 으로 만 듭 니 다. 나머지 부분 을 계속 이렇게 나 누 면 (n - 1) 번 을 자 른 후에 마지막 에 남 은 사각형 바둑판 과 함께 n 개의 사각형 바둑판 이 있 습 니 다.(매번 절단 할 때마다 바둑판 격자 의 변 을 따라 만 진행 할 수 있 습 니 다) 원래 바둑판 의 모든 칸 은 하나의 가치 가 있 고 사각형 바둑판 의 총 점 은 각 칸 의 가치 의 합 으로 나 눌 수 있 습 니 다.지금 은 바둑판 을 상술 한 규칙 에 따라 n 개의 직사각형 바둑판 으로 나 누고 각 직사각형 바둑판 의 총 점 의 평균 방 차 를 최소 화해 야 한다.평균 분산, 그 중에서 평균 값, xi 는 제 i 블록 사각형 바둑판 의 총 점 이다.
제 시 된 바둑판 과 n 을 프로 그래 밍 하여 O 의 최소 값 을 구하 십시오.
사고방식: lrj 에서 P116 의 예제.dp [k] [x1] [y1] [x2] [y2]: 왼쪽 상단 좌 표 는 (x1, y1) 이 고 오른쪽 아래 좌 표 는 (x2, y2) 의 바둑판 으로 k 회 절단 후 얻 은 k + 1 개의 사각형 의 총 점 제곱 과 최소 치 를 설정 합 니 다.s [x1] [y1] [x2] [y2]: 왼쪽 상단 좌 표 는 (x1, y1) 이 고 오른쪽 아래 좌 표 는 (x2, y2) 이다.의 바둑판 의 총화 제곱 상태 전이 방정식 dp [k] [x1] [y1] [x2] [y2] =  1) 가로로 나 누 기:   min(dp[k-1][x1][y1][f][y2]+s[f+1][y1][x2][y2] , dp[k-1][f+1][y1][x2][y2]+s[x1][y1][f][y2]); 2) 세로 로 나 누 기:   min(dp[k-1][x1][y1][x2][f]+s[x1][f+1][x2][y2], dp[k-1][x1][f+1][x2][y2]+s[x1][y1][x2][f]);

/* 
dp[k][x1][y1][x2][y2]:      (x1,y1)，      (x2,y2)
   ，     k      k+1            .

s[x1][y1][x2][y2]:      (x1,y1)，      (x2,y2)
         


 dp[k][x1][y1][x2][y2] = 
1)     ：    min(dp[k-1][x1][y1][f][y2]+s[f+1][y1][x2][y2]
                , dp[k-1][f+1][y1][x2][y2]+s[x1][y1][f][y2]);

2)     ：    min(dp[k-1][x1][y1][x2][f]+s[x1][f+1][x2][y2]
                , dp[k-1][x1][f+1][x2][y2]+s[x1][y1][x2][f]);
 */ 
#include <stdio.h>
#include <memory.h>
#include <math.h>
int n;
int dp[16][10][10][10][10];
int data[10][10];
int s[10][10][10][10];
void get_sum(int x1,int y1,int x2,int y2) {
	int i,j,sum;

	sum=0;

	if (s[x1][y1][x2][y2]!=0)
		return;
	for (i=x1;i<=x2;i++) {
		for (j=y1;j<=y2;j++) {
			sum=sum+data[i][j];
		}
	}
	s[x1][y1][x2][y2]=sum*sum;
}
int min_num(int a,int b) {
	if (a>b)
		return b;
	return a;
}
int main()
{
	int i,j,k,g,h,l,temp;
	double sum,average,result;

	scanf("%d",&n);
	sum=0;
	for (i=1;i<=8;i++) {
		for (j=1;j<=8;j++) {
			scanf("%d",&data[i][j]);
			sum+=data[i][j];
		}
	}
	average=sum/n;
	memset(s,0,sizeof(s));
	for (i=1;i<=8;i++) {
		for (j=1;j<=8;j++) {
			for (g=i;g<=8;g++) {
				for (h=j;h<=8;h++) {
					get_sum(i,j,g,h);
					dp[0][i][j][g][h]=s[i][j][g][h];

				}
			}
		}
	}
	for (k=1;k<n;k++) {
		for (i=1;i<=8;i++) {
			for (j=1;j<=8;j++) {
				for (g=i;g<=8;g++) {
					for (h=j;h<=8;h++) {
						dp[k][i][j][g][h]=10000000;
						for (l=i;l<g;l++) {
							get_sum(l+1,j,g,h);
							temp=min_num(dp[k-1][i][j][l][h]+s[l+1][j][g][h],dp[k-1][l+1][j][g][h]+s[i][j][l][h]);
							dp[k][i][j][g][h]=min_num(temp, dp[k][i][j][g][h]);
						}
						for (l=j;l<h;l++) {
							get_sum(i,l+1,g,h);
							temp=min_num(dp[k-1][i][j][g][l]+s[i][l+1][g][h],dp[k-1][i][l+1][g][h]+s[i][j][g][l]);
							dp[k][i][j][g][h]=min_num(temp, dp[k][i][j][g][h]);
						}
					}
				}
			}
		}
	}
	result=(double)dp[n-1][1][1][8][8]/n-average*average;
	printf("%.3lf
",sqrt(result));
	return 0;
}