「题目背景」
小奇总是在数学课上思考奇怪的问题。
「问题描述」
给定一个n*m的矩阵，矩阵中的每个元素aij为正整数。
接下来规定
1.合法的路径初始从矩阵左上角出发，每次只能向右或向下走，终点为右下角。
2.路径经过的n+m-1个格子中的元素为A1,A2…A(n+m-1)，Aavg为Ai的平均数，路径的V值为(n+m-1)*∑(Ai-Aavg) ^2
(1<=i<=n+m-1)
求V值最小的合法路径，输出V值即可，有多组测试数据。
「输入格式」
第一行包含一个正整数T，表示数据组数。
对于每组数据：
第一行包含两个正整数n和m，表示矩阵的行数和列数。
接下来n行，每行m个正整数aij，描述这个矩阵。
「输出格式」
对于每次询问，输出一行一个整数表示要求的结果
「样例输入」
1
2 2
1 2
3 4
「样例输出」
14
「数据范围」
对于30%的数据 n<=10，m<=10
有另外40%的数据 n<=15 m<=15，矩阵中的元素不大于5
对于100%的数据 T<=5，n<=30，m<=30，矩阵中的元素不大于30
code
#include<bits/stdc++.h> #define inf 100000000 #define ll long long #define N (n+m)*30 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int ans; int T,n,m; int a[35][35]; int f[1805][35][35]; void dp() { f[a[1][1]][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<=N;k++) if(f[k][i][j]!=1000000) { int x=i+1,y=j,v=a[x][y]; f[k+v][x][y]=min(f[k+v][x][y],f[k][i][j]+v*v); x=i,y=j+1,v=a[x][y]; f[k+v][x][y]=min(f[k+v][x][y],f[k][i][j]+v*v); } for(int i=1;i<=N;i++) if(f[i][n][m]!=1000000) ans=min(ans,(n+m-1)*f[i][n][m]-i*i); } int main() { T=read(); while(T--) { ans=inf; n=read();m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<=N;k++) f[k][i][j]=1000000; dp(); printf("%d\n",ans); } return 0; }
原文：https://www.cnblogs.com/xcwang/p/11629486.html