题意：从(1, 1)走到(n, m)，每次往右或往下走，问(N+M−1)∑(Ai−Aavg)2 的最小值
分析：展开式子得到(N+M−1)∑(Ai2) - (∑(Ai))2的最小值。用普通的搜索要不超时要不爆内存，用dp。注意到和的值很小，最多59*30，所以dp[i][j][k]表示当走到(i, j)点时和为k的最小的平方和，两个方向转移。
/************************************************
* Author :Running_Time
* Created Time :2015/9/28 星期一 08:16:33
* File Name :I.cpp
************************************************/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 33;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
int dp[N][N][N*2*N];
int a[N][N];
int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
int n, m; scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
scanf ("%d", &a[i][j]);
}
}
int S = 59 * 30;
memset (dp, INF, sizeof (dp));
dp[1][1][a[1][1]] = a[1][1] * a[1][1];
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
for (int k=0; k<=S; ++k) {
int &u = dp[i][j][k];
if (u == INF) continue;
if (i + 1 <= n) {
int &v = dp[i+1][j][k+a[i+1][j]];
v = min (v, u + a[i+1][j] * a[i+1][j]);
}
if (j + 1 <= m) {
int &v = dp[i][j+1][k+a[i][j+1]];
v = min (v, u + a[i][j+1] * a[i][j+1]);
}
}
}
}
int ans = INF;
for (int i=0; i<=S; ++i) {
if (dp[n][m][i] == INF) continue;
ans = min (ans, (n + m - 1) * dp[n][m][i] - i * i);
}
printf ("Case #%d: %d
", ++cas, ans);
}
return 0;
}