题意:
从左上角走到右下角,路径的最小方差是多少,要求输出方差*(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;
}
版权声明:本文为wdcjdtc原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。