又一个用lf输出的。。。

> #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));
> 	}
> 
> }

• +1 (8) Jimng 2013-12-26 04:18:48