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;
}