ＨＤＵ－５４９２　Find a path　（枚举＋ＤＰ）

# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;

double dp[35][35];
int mp[35][35],n,m;

double DP(int eva)
{
    double k=n+m-1.0;
    dp[n-1][m-1]=(mp[n-1][m-1]-eva/k)*(mp[n-1][m-1]-eva/k);
    for(int i=n-2;i>=0;--i)
        dp[i][m-1]=(mp[i][m-1]-eva/k)*(mp[i][m-1]-eva/k)+dp[i+1][m-1];
    for(int i=m-2;i>=0;--i)
        dp[n-1][i]=(mp[n-1][i]-eva/k)*(mp[n-1][i]-eva/k)+dp[n-1][i+1];
    for(int i=n-2;i>=0;--i)
        for(int j=m-2;j>=0;--j)
            dp[i][j]=(mp[i][j]-eva/k)*(mp[i][j]-eva/k)+min(dp[i+1][j],dp[i][j+1]);
    return (n+m-1)*dp[0][0];
}

int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                scanf("%d",&mp[i][j]);

        double ans=1e10;
        for(int i=0;i<=1770;++i)
            ans=min(ans,DP(i));
        printf("Case #%d: %.0lf\n",++cas,ans);
    }
    return 0;
}