错误答案风雨不动安如山,求调
查看原帖
错误答案风雨不动安如山,求调
950927
_luo_gu楼主2024/8/23 10:01
#include <bits/stdc++.h>
using namespace std ;
//f[x][y][xx][yy][kk]该值表示以(x,y)为左上,(xx,yy)为右下,分割kk后的(xi-均值)^2 
double f[20][20][20][20][20] , junzhi ;
int n , m , k , a[11][11] , sum[11][11];
bool mar[20][20][20][20][20] ;
double search( int x , int y , int xx , int yy , int kk ){
	if (kk > (xx - x + 1) * (yy - y + 1)) {
		return 2147483647;
	}
	if( f[x][y][xx][yy][kk] ){
		return f[x][y][xx][yy][kk] ;
	}
	if( kk <= 1 ){
		double i = sum[xx][yy] + sum[x-1][y-1] - sum[x-1][yy] - sum[xx][y-1] ;
		i = f[x][y][xx][yy][kk] = ( i - junzhi )*(i - junzhi) ;
		mar[x][y][xx][yy][kk] = true ;
		return i ;
	}	
	double ans = 100000 ;
	for ( int i = x+1; i < xx ; i ++ ){
		for( int j = 1 ; j < kk ; j ++ ){
			ans = min ( ans , (search( x , y , i , yy , j )+search( i+1,y,xx,yy,kk-j)))	;		
		}
	}
	for( int i = y+1; i < yy ; i ++ ){
		for( int j = 1 ; j < kk ; j ++ ){
			ans = min ( ans , (search( x , y , xx , i , j )+search( x,i+1,xx,yy,kk-j)))	;		
		}
	}
	f[x][y][xx][yy][kk] = ans ;
	mar[x][y][xx][yy][kk] = true ;
	return ans ;
}   
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for( int i = 1 ;i <= n ; i ++ ){
		for( int j = 1 ; j <= m ; j ++ ){
			scanf("%d" , &a[i][j] );
			sum[i][j] = a[i][j] ;
		}
	}
	for( int i = 1 ; i <= n ; i ++ ){
		for( int j = 1 ; j <= m ; j ++ ){
			sum[i][j] += (sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]);
		}
	}
	junzhi = sum[n][m] / k ;
	double ans = search( 1 , 1 , n , m , k );
	ans /= k ;
	ans = sqrt(ans);
	printf("%.2f",ans);
	return 0 ;
}   

感谢aker,好人一生平安

2024/8/23 10:01
加载中...