#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define N 9
#define M 16
long double dp[N][N][N][N][M];
bool vi[N][N][N][N][M];
long double s[N][N];
int d[N][N];
long double average_x;
inline long double MIN(long double x,long double y){
	if(x<y) return x;
	return y;
}
long double dfs(int stx,int sty,int edx,int edy,int n){
	if(vi[stx][sty][edx][edy][n]){
		return dp[stx][sty][edx][edy][n];
	}
	vi[stx][sty][edx][edy][n]=true;
	if(n==1){
		long double total_x=s[edx][edy]-s[edx][sty-1]-s[stx-1][edy]+s[stx-1][sty-1];
		return dp[stx][sty][edx][edy][n]=pow(total_x-average_x,2);
	}

	long double ret=1e18;
	for(int i=stx;i<edx;i++){
		ret=MIN(dfs(stx,sty,i,edy,1)+dfs(i+1,sty,edx,edy,n-1),ret);
		ret=MIN(dfs(stx,sty,i,edy,n-1)+dfs(i+1,sty,edx,edy,1),ret);
	}
	for(int i=sty;i<edy;i++){
		ret=MIN(dfs(stx,sty,edx,i,1)+dfs(stx,i+1,edx,edy,n-1),ret);
		ret=MIN(dfs(stx,sty,edx,i,n-1)+dfs(stx,i+1,edx,edy,1),ret);
	}
	return dp[stx][sty][edx][edy][n]=ret;
}
int main()
{
	int n;
	while(scanf(" %d",&n)==1){
		for(int i=1;i<=8;i++){
			for(int j=1;j<=8;j++){
				scanf(" %d",&d[i][j]);
				s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+d[i][j];
			}
		}
		average_x = s[8][8]/n;
		memset(vi,0,sizeof(vi));
		dfs(1,1,8,8,n);
		printf("%.3lf\n",sqrt(dp[1][1][8][8][n]/n));
	}

}

• Re:1y的代码 我竟然跳了那么久 g++和c++就茶那么多吗？ c++过，g++wa (1492) Shinjikun 2012-11-25 03:57:20
  • +1 (8) Jimng 2013-12-26 04:18:48