Description

在矩阵中，找一条到从 \((1,1)\) 到 \((n,m)\)（只能向上，右走）的路径，使路径上方差最小。输出方差平方乘 \(n+m-1\) 的结果。

对于所有数据，\(1\leq n,m,A_{i,j}\leq30\)。

Solution

设路径上的数为 \(A_{1},A_{2},A_{3},\cdots,A_{n+m-1}\)，\(\overline{A}\) 为其平均数，则答案为 \(\displaystyle(n+m-1)\sum_{i=1}^{n+m-1}(A_i-\overline{A})^2\)。

推一下柿子，令 \(\displaystyle S=\sum_{i=1}^{n+m-1}A_i\)，则：

\[(n+m-1)\sum_{i=1}^{n+m-1}(A_i-\overline{A})^2=\dfrac{1}{n+m-1}\sum_{i=1}^{n+m-1}((n+m-1)A_i-S)^2 \]

枚举 \(S\)，令 \(f_{i,j}\) 为走到 \((i,j)\) 的最小代价，然后计算即可。

发现对于枚举的 \(S\) 不等于选出路径上数的和的情况，一定不如等于选出路径上数的和的情况优，所以不用管。

时间复杂度 \(\mathcal{O}(nmf)\)，\(f\) 为从 \((1,1)\) 到 \((n,m)\)的路径的最大的和。在 \(n,m,A_{i,j}\) 同级的情况下相当于 \(O(n^4)\)。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Milkcat {
    typedef long long LL;
    const int N = 105;
    LL n, m, ans, a[N][N], f[N][N];
    LL sqr(LL x) { return x * x; }
	LL solve(LL S) {
		f[1][0] = 0;
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= m; j ++)
				f[i][j] = min(f[i - 1][j], f[i][j - 1]) + sqr((n + m - 1) * a[i][j] - S);
		return f[n][m];
	}
    int main() {
		memset(f, 0x3f, sizeof f);
        cin >> n >> m, ans = LLONG_MAX;
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= m; j ++)
				cin >> a[i][j];
		for (int i = 1; i <= 1800; i ++)
			ans = min(ans, solve(i));
		cout << ans / (n + m - 1) << '\n';
		return 0;
    }
}
int main() {
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}