为啥不对啊这记忆化。。服了
查看原帖
为啥不对啊这记忆化。。服了
736891
Eternality楼主2022/10/14 18:06
#include<bits/stdc++.h>
using namespace std;
#define min(a,b) a<b ? a:b

int n,m,kk;
double dp[11][11][11][11][11],A[11][11],sum,ave;

double dfs(int a,int b,int c,int d,int k)
{
	if(dp[a][b][c][d][k]!=0)return dp[a][b][c][d][k];
	if(k==0)
	{
		double t=0;
		for(int i=a;i<=b;i++)
		{
			for(int j=c;j<=d;j++)
			{
				t+=A[i][j];
			}
		}
		return dp[a][b][c][d][k]=(t-ave)*(t-ave);
	}
	double ans=1e9+666;
	if(b-a+1>1)
	for(int i=a;i<b;i++)
	{
		for(int step=0;step<k;step++)
		{
			ans=min(ans,dfs(a,i,c,d,step)+dfs(i+1,b,c,d,k-step-1));
		}
	}
	if(d-c+1>1)
	for(int i=c;i<d;i++)
	{
		for(int step=0;step<k;step++)
		{
			ans=min(ans,dfs(a,b,c,i,step)+dfs(a,b,i+1,d,k-step-1));
		}
	}
	return dp[a][b][c][d][k]=ans;
}

int main()
{
	scanf("%d%d%d",&n,&m,&kk);
	memset(dp,0,sizeof dp);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%lf",&A[i][j]);
			sum+=A[i][j];
		}
	}
	ave=sum/kk;
//	cout<<ave<<endl;
	printf("%.2lf",sqrt(dfs(1,m,1,n,kk-1)/kk));
	return 0;
}
2022/10/14 18:06
加载中...