题意：

在一张N*M的图上，每个点都有权值，寻找一条从（1,1）到（n，m）的路径，使得

(n+m-1)*sigma(Ai-Aavg)最小

其中Aavg是路径上Ai的平均数

 

题解

看题目是一个DP，但是路径平均值得存在使得状态很难定义。

所以我们进行变形，将和式展开之后，得到ans=(n+m-1)*S1-S2;

其中S1是路径上所有数的平方和，S2为路径上数的和的平方。

也就是要求S1最小的同时S2最大。

dp[i][j][s]表示到达(i,j)时平方和为s时和的的最小值，答案通过枚举所有s取得

 

#include
     
      #define clr(x,y) memset((x),(y),sizeof(x))using namespace std;typedef long long LL;const int maxn=30;const int inf=1e8;int mp[maxn+5][maxn+5];int dp[maxn+5][maxn+5][2*maxn*maxn+5];int n,m;void solve(int iCase){    scanf("%d%d",&n,&m);    for (int i=1;i<=n;++i)    {        for (int j=1;j<=m;++j)        {            scanf("%d",&mp[i][j]);        }    }    for (int i=1;i<=n;++i)        for (int j=1;j<=m;++j)            for (int k=0;k<=2*maxn*maxn;++k)                dp[i][j][k]=inf;    dp[1][1][mp[1][1]]=mp[1][1]*mp[1][1];    for (int i=1;i<=n;++i)    {        for (int j=1;j<=m;++j)        {            if (i==1 && j==1) continue;            for (int k=0;k<=2*maxn*maxn;++k)            {                if (i-1>=1 && k>=mp[i][j])                    dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k-mp[i][j]]+mp[i][j]*mp[i][j]);                if (j-1>=1 && k>=mp[i][j])                    dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k-mp[i][j]]+mp[i][j]*mp[i][j]);            }        }    }    int ans=inf;    for (int k=0;k<=2*maxn*maxn;++k)    {        if (dp[n][m][k]==inf) continue;        int tmp=(n+m-1)*dp[n][m][k]-k*k;        ans=min(ans,tmp);    }    printf("Case #%d: %d\n",iCase,ans);}int main(void){    #ifdef ex    freopen ("../in.txt","r",stdin);    //freopen ("../out.txt","w",stdout);    #endif    int T;    scanf("%d",&T);    for (int i=1;i<=T;++i)    {        solve(i);    }}