题意：
给你一个n*m的地图，每个点都有它的权值。每次只能向下或者向左走，问从（1,1）到（n，m）怎么走使得
最小。
我们发现上式等于走过的路程的方差*（N+M-1）^2，又D（x）=E（x^2）+（E（x）)^2
所以可以化简为（N+M-1）*s1-s2 (s1是ai的平方和 s2是ai和的平方)
然后ai的和最大为59*30 所以可以暴力枚举和
ACcode
#include <bits/stdc++.h> #define maxn 32 #define inf 0x3f3f3f3f using namespace std; int a[maxn][maxn]; int dp[maxn][maxn][1800]; int main(){ int loop,n,m,cnt=1; scanf("%d",&loop); while(loop--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&a[i][j]); 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 t=0;t<=59*30;++t) if(dp[i][j][t]!=inf){ if(i+1<=n) dp[i+1][j][t+a[i+1][j]]=min(dp[i+1][j][t+a[i+1][j]],dp[i][j][t]+a[i+1][j]*a[i+1][j]); if(j+1<=m) dp[i][j+1][t+a[i][j+1]]=min(dp[i][j+1][t+a[i][j+1]],dp[i][j][t]+a[i][j+1]*a[i][j+1]); } int ans=inf; for(int i=0;i<=59*30;++i) if(dp[n][m][i]!=inf) ans=min(ans,(n+m-1)*dp[n][m][i]-i*i); printf("Case #%d: %d\n",cnt++,ans); } return 0; }
