求调
查看原帖
求调
1228886
skyx楼主2025/2/7 20:11
#include<bits/stdc++.h>
using namespace std;
#define db double
int a[10][10];
db dp[20][20][20][20][20];
int pre[10][10];
int main()
{
int n;
cin>>n;
for(int i=1;i<=8;i++)
{
	for(int j=1;j<=8;j++)
	{
		scanf("%d",&a[i][j]);
	}
}
for(int i=1;i<=8;i++)
{
	for(int j=1;j<=8;j++)
	{
		pre[i][j]=a[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
		cout<<pre[i][j]<<" "; 
	}
	cout<<endl;
}
	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++)
	{
		db tot=(db)(pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1])-(pre[8][8]*1.0)/(n); 
		dp[x1][y1][x2][y2][1]=tot*tot/n;			
	}}}}
	
	
		for(int k=2;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=x2;y2<=8;y2++)
	{
		dp[x1][y1][x2][y2][k]=1e9;
		            for(int i=x1;i<x2;i++)
		{
				dp[x1][y1][x2][y2][k]=min(dp[x1][y1][i][y2][k-1]+dp[i+1][y1][x2][y2][1],
				min(dp[x1][y1][i][y2][1] + dp[i+1][y1][x2][y2][k-1], 
				dp[x1][y1][x2][y2][k]));
		}
		for (int i=y1;i<y2;i++)
		{
			dp[x1][y1][x2][y2][k]=min(dp[x1][y1][x2][i][1] + dp[x1][i+1][x2][y2][k - 1],
			 min(dp[x1][y1][x2][i][k-1] + dp[x1][i+1][x2][y2][1], 
			 dp[x1][y1][x2][y2][k]));
		}
	}}}}}

	printf("%.3lf",sqrt(dp[1][1][8][8][n]));
	return 0;
}
2025/2/7 20:11
加载中...