求组
查看原帖
求组
714900
zyzbldnb楼主2023/7/21 10:39
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=10,M=20;
int f[N][N][N][N][M],s[N][N];
int get(int x1,int y1,int x2,int y2)
{
	int sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
	return sum*sum;
}
int dfs(int x1,int y1,int x2,int y2,int k)//分
{
	int w=f[x1][y1][x2][y2][k];
	if(w>0) return w;
	if(k==1) return f[x1][y1][x2][y2][k]=get(x1,y1,x2,y2);
	w=1e8;
	for(int i=x1;i<x2;i++)
	{
		w=min(w,dfs(x1,y1,i,y2,k-1)+get(i+1,y1,x2,y2));
		w=min(w,dfs(i+1,y1,x2,y2,k-1)+get(x1,y1,i,y2));
	}
	for(int i=y1;i<y2;i++)
	{
		w=min(w,dfs(x1,y1,x2,i,k-1)+get(x1,i+1,x2,y2));
		w=min(w,dfs(x1,i+1,x2,y2,k-1)+get(x1,y1,x2,i));
	}
	return f[x1][x2][y1][y2][k]=w;
}
int main()
{
	int n,a;
	cin>>n;
	for(int i=1;i<=8;i++)
	for(int j=1;j<=8;j++)
	{
	cin>>a;
	s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a;	
	}
	memset(f,-1,sizeof(f));
//	double x=1.0*s[8][8]/n,ans=sqrt(1.0*dfs(1,1,8,8,n)/n-x*x);
	//cout<<x<<endl<<dfs(1,1,8,8,n);
//	printf("%.3lf",ans);
    cout<<dfs(1,1,8,8,n);
	return 0;
}
2023/7/21 10:39
加载中...