@[Eternality](/user/736891) 也许和 [这个](https://www.luogu.com.cn/discuss/509551) 很像。
~~草,三倍经验!~~
by Error_Eric @ 2022-10-14 18:11:30
考虑全是 $0$,这记忆了和没记忆一样,所以 ``dp`` 初始赋极大值。
by Error_Eric @ 2022-10-14 18:12:58
@[Error_Eric](/user/217300)
意思就是加上个条件,必须从合法情况转移过来么?
by Eternality @ 2022-10-14 18:42:50
@[Eternality](/user/736891) hmmm...
我的最早一版代码的问题是在这里,但是你的。。。
考虑
```plain
1 1 1
0
```
``f`` 数组初值是 $0$,但是我答案也可能是 $0$ 啊?我不能通过当前位置是不是 $0$ 来决策要不要向下转移。
初值赋个 $sum\times sum+5$ 就不会有这种问题。
但是这样就要注意有可能无解会导致停在 $sum\times sum+5$ 不变,所以还要判断是否有解。
by Error_Eric @ 2022-10-14 18:46:26
@[Error_Eric](/user/217300)
还是不对(我真搞不懂DP)
by Eternality @ 2022-10-14 18:55:38
@[Error_Eric](/user/217300)
不管怎样,谢谢啦
by Eternality @ 2022-10-14 19:04:07
@[Eternality](/user/736891)
```cpp
#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;
int aij;
double dfs(int a,int b,int c,int d,int k)
{
if(fabs(dp[a][b][c][d][k]-(1e9+666))>0.5) 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;
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));
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=0;i<=10;i++)
for(int j=0;j<=10;j++)
for(int ii=0;ii<=10;ii++)
for(int jj=0;jj<=10;jj++)
for(int qk=0;qk<=10;qk++)
dp[i][j][ii][jj][qk]=1e9+666;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&aij),A[i][j]=aij,sum+=A[i][j];
ave=sum/kk;
// cout<<ave<<endl;
printf("%.2lf",sqrt(dfs(1,n,1,m,kk-1)/kk));
return 0;
}
```
by Error_Eric @ 2022-10-14 19:07:01
@[Eternality](/user/736891) 你原来的 dfs 初始传参还传错了...
by Error_Eric @ 2022-10-14 19:08:46
@[Error_Eric](/user/217300) 谢谢大佬%%%,对不起
by Eternality @ 2022-10-14 19:17:05
@[Eternality](/user/736891) 没啥好对不起的qwq,谁不是从萌新过来的呢?
(尽管我现在还是很菜。)
by Error_Eric @ 2022-10-14 19:50:17