博客

题意：

从左上角走到右下角，路径的最小方差是多少，要求输出方差*（N+M-1）

思路：

首先我们化简一下方差公式

发现答案为（n+m-1)*Σai^2-sum^2  sum为路径取的数的和

因为a[i]<=30 所以综合为 59*30

我们设dp[i][j][k]代表走到（i,j）位置和为k的最小平方和是多少

然后转移就好了。

代码：

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#include"map"
#include"stack"
#define eps 1e-8
using namespace std;
#define ll __int64
#define MAXN 200004
ll dp[33][33][61*32];
int v[33][33];
int main()
{
    int t,cas=1;
    cin>>t;
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(v,-1,sizeof(v));
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&v[i][j]);
        for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=59*30;k++) dp[i][j][k]=9999999;
        dp[1][1][v[1][1]]=v[1][1]*v[1][1];
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                for(int k=0;k<=59*30;k++)
                {
                    if(dp[i][j][k]>=9999999) continue;

                    dp[i][j+1][k+v[i][j+1]]=min(dp[i][j+1][k+v[i][j+1]],dp[i][j][k]+v[i][j+1]*v[i][j+1]);
                    dp[i+1][j][k+v[i+1][j]]=min(dp[i+1][j][k+v[i+1][j]],dp[i][j][k]+v[i+1][j]*v[i+1][j]);
                }
            }
        }
        ll ans=99999999999999LL;
        ll cnt=m+n-1;
        for(int i=0;i<=59*30;i++)
        {
            if(dp[n][m][i]==9999999) continue;
            ans=min(ans,cnt*dp[n][m][i]-i*i);
        }
        printf("Case #%d: %I64d\n",cas++,ans);

    }
    return 0;
}