- #include<stdio.h>
- #include <math.h>
- #include <algorithm>
- #include <math.h>
- #include <string.h>
- #include <bitset>
- #include <iostream>
- using namespace std;
- #define LL long long
- int n,m,k;
- int a[31][31];
- int f[31][31];
- #define sqr(x) ((x)*(x))
- int cal(int avg)
- {
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- {
- int t=sqr(k*a[i][j]-avg);
- if(i==1&&j==1)
- f[i][j]=t;
- else if(i==1)
- f[i][j]=f[i][j-1]+t;
- else if(j==1)f[i][j]=f[i-1][j]+t;
- else f[i][j]=min(f[i][j-1],f[i-1][j])+t;
- }
- return f[n][m]/k; // 不同的路径里只有枚举的 avg== 真实的 avg 时, 路径方差最小
- }
- int main()
- {
- freopen("in.txt","r",stdin);
- int t;
- scanf("%d",&t);
- for(int cas=1;cas<=t;cas++)
- {
- scanf("%d%d",&n,&m);
- k=n+m-1;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- scanf("%d",&a[i][j]);
- int ans=1e9;
- for(int i=0,sz=k*30;i<=sz;i++)
- {
- ans=min(ans,cal(i));
- }
- printf("Case #%d: %d\n",cas,ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2773104.html