POJ 1191

WA가 십여 발을 썼어요. 저는 파이브 망치예요...
DP 부분에는 문제가 없으며 구덩이가 몇 개 있다

DP 그룹을 설계할 때 최소값을 INF로 초기화했다. 문제는 이 INF가 너무 작으면 안 된다는 것이다. 적어도 6400의 제곱보다 크면 안 된다. 그러나 너무 크면 안 된다. 내가 처음에 0x7f7f7f7f7f7f로 설정했는데 나중에 보니 이 수가 너무 커서 int가 넘쳐났다

.

반올림 소수에 대해 이전에 습관적으로%.3f를 사용했지만 이것은 반올림을 실현하지 못하면 그는 자동으로 지위 숫자

를 잃게 된다.

사실 이것은 귀환으로 하는 것이 더 좋다. 내가 처음에 발생한 문제는 귀환+기억화 검색을 하면 사실 피할 수 있다

아무튼 마음이 아파요...

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn= 20;
const int INF= 0x3f3f3f3f;

int m[10][10], s[10][10];
int dp[maxn][10][10][10][10];

int SqSum(int x1, int y1, int x2, int y2)
{
	--x1;
	--y1;
	int sm= s[x1][y1]+s[x2][y2]-s[x2][y1]-s[x1][y2];
	return sm*sm;
}
void Init()
{
	memset(dp, 0x3f, sizeof(dp));
	memset(s, 0, sizeof(s));

	for (int i= 1; i<= 8; ++i){
		int ls= 0;
		for (int j= 1; j<= 8; ++j){
			ls+= m[i][j];
			s[i][j]= s[i-1][j]+ls;
		}
	}

	for (int x1= 1; x1<= 8; ++x1){
		for (int y1= 1; y1<= 8; ++y1){
			for (int x2= x1; x2<= 8; ++x2){
				for (int y2= y1; y2<= 8; ++y2){
					int sq= SqSum(x1, y1, x2, y2);
					dp[0][x1][y1][x2][y2]= sq;
				}
			}
		}
	}
}

int main()
{
	int n;
	double sg, sg2, xav, xsm= 0.0;
	scanf("%d", &n);

	for (int i= 1; i<= 8; ++i){
		for (int j= 1; j<= 8; ++j){
			scanf("%d", &(m[i][j]));
			xsm+= m[i][j];
		}
	}
	Init();

	xav= xsm/n;

	// the range of k can be optimized
	for (int k= 1; k< n; ++k){ 	
		for (int x1= 1; x1<= 8; ++x1){
			for (int y1= 1; y1<= 8; ++y1){
				for (int x2= x1; x2<= 8; ++x2){
					for (int y2= y1; y2<= 8; ++y2){
						int a, b, tmp, sq;
						tmp= INF;

						for (int x= x1; x< x2; ++x){
							sq= dp[0][x+1][y1][x2][y2];
							a= dp[k-1][x1][y1][x][y2]+sq;
							sq= dp[0][x1][y1][x][y2];
							b= dp[k-1][x+1][y1][x2][y2]+sq;
							tmp= min(tmp, min(a, b));
						}
						for (int y= y1; y< y2; ++y){
							sq= dp[0][x1][y+1][x2][y2];
							a= dp[k-1][x1][y1][x2][y]+sq;
							sq= dp[0][x1][y1][x2][y];
							b= dp[k-1][x1][y+1][x2][y2]+sq;
							tmp= min(tmp, min(a, b));
						}

						dp[k][x1][y1][x2][y2]= tmp;
					}
				}
			}
		}
	}

	sg2= double(dp[n-1][1][1][8][8])/double(n)-xav*xav;
	sg= floor(1000*sqrt(sg2)+0.5)/1000;

	printf("%.3f
", sg);
	return 0;
}