[CSP-S模拟测试]:小奇的矩阵(matrix)（DP+数学）

题目背景

小奇总是在数学课上思考奇怪的问题。

题目描述

给定一个$n\times m$的矩阵，矩阵中的每个元素$a_{i,j}$为正整数。
接下来规定：
$1.$合法的路径初始从矩阵左上角出发，每次只能向右或向下走，终点为右下角。
$2.$路径经过的$n+m-1$个格子中的元素为$A_1,A_2...A_{(n+m-1)}$，$Aavg$为$A_i$的平均数，路径的$V$值为$(n+m-1)\times \sum \limits_{i=1}^{n+m-1}{(A_i-Advg)}^2$
求$V$值最小的合法路径，输出$V$值即可，有多组测试数据。

输入格式

第一行包含一个正整数$T$，表示数据组数。
对于每组数据：
第一行包含两个正整数$n$和$m$，表示矩阵的行数和列数。
接下来$n$行，每行$m$个正整数$a_{i,j}$，描述这个矩阵。

输出格式

对于每次询问，输出一行一个整数表示要求的结果。

样例

样例输入：

1
2 2
1 2
3 4

样例输出：

数据范围与提示

对于$30\%$的数据$n\leqslant 10$，$m\leqslant 10$。
有另外$40\%$的数据$n\leqslant 15$，$m\leqslant 15$，矩阵中的元素不大于$5$。
对于$100\%$的数据$T\leqslant 5$，$n\leqslant 30$，$m\leqslant 30$，矩阵中的元素不大于$30$。

题解

又是令人头疼的数学，而数学题就得化式子（但是你说你知道方差公式那我也没辙）。

那就来化式子：

$(n+m-1)\sum{(A_i-Aavg)}^2$
$=|(n+m-1)\times \sum({A_i}^2-2\times A_i\times Aavg+{Aavg}^2)|$
$=|(n+m-1)\times \sum{A_i}^2-(n+m-1)\times 2\times \sum (A_i\times Aavg)+(n+m-1)\times \sum{Aavg}^2|$
$=|(n+m-1)\times \sum{A_i}^2-(n+m-1)\times 2\times \frac{\sum{A_i}^2}{n+m-1}+(n+m-1)\times \frac{{Aavg}^2}{n+m-1}|$
$=|-(n+m-1)\times \sum{A_i^2}-{Aavg}^2|$
$=|{Aavg}^2-(n+m-1)\times \sum{A_i}^2|$

我们又发现矩阵中元素不大于$30$，既然它出现，必然有它的意义。

考虑从这里入手，我们现在就来考虑$DP$，定义dp[i][j][k]表示到点(i,j)，和为k，平方和的最小值。

那么状态转移方程即为：$dp[i][j][k]=\min(dp[i-1][j][k-x[i][j]],dp[i][j-1][k-x[i][j]])+x[i][j]\times x[i][j]$

而我们统计答案的时候只需要找$\min(dp[n][m][i]\times (n+m-1)-i\times i)$即可。

时间复杂度：$\Theta(30\times n\times m\times (n+m))$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,m;

int Map[50][50];

int dp[50][50][2000];

int ans,maxn;

void pre_work()

{

	ans=1<<30;

	memset(dp,0x3f,sizeof(dp));

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		pre_work();

		scanf("%d%d",&n,&m);

		for(int i=1;i<=n;i++)

			for(int j=1;j<=m;j++)

				scanf("%d",&Map[i][j]);

		dp[1][1][Map[1][1]]=Map[1][1]*Map[1][1];

		for(int i=1;i<=n;i++)

			for(int j=1;j<=m;j++)

				for(int k=Map[i][j];k<=(n+m-1)*30;k++)

					dp[i][j][k]=min(dp[i][j][k],min(dp[i-1][j][k-Map[i][j]],dp[i][j-1][k-Map[i][j]])+Map[i][j]*Map[i][j]);

		for(int i=Map[n][m];i<=(n+m-1)*30;i++)

			if(dp[n][m][i]<1061109567)

				ans=min(ans,dp[n][m][i]*(n+m-1)-i*i);

		printf("%d\n",ans);

	}

	return 0;

}

rp++

巴特西