最平坦的路线题解
题目描述
现有一个城市的地图，地图是一个 n × m n\times m n×m的矩形，现在要在这个城市中旅行，旅行的起点左上角坐标为 ( 1 , 1 ) (1,1) (1,1)，终点右下角坐标为 ( n , m ) (n,m) (n,m)。地图上记录了每一个点的高度，坐标为 ( x , y ) (x,y) (x,y)的位置，高度为 h x , y h_{x,y} hx,y。每次只能向右或向下，不能走出城市，只能在整数点转弯。请你计算出一条路线，使得经过的点的高度的方差最小。输出最小的方差乘 ( n + m − 1 ) 2 (n+m-1)^2 (n+m−1)2后的值。
方差的定义：对于 k k k个整数 x 1 , x 2 , ⋯ , x k x_1,x_2,\cdots,x_k x1,x2,⋯,xk，这 k k k个数的方差为 S 2 = ( x 1 − x ‾ ) 2 + ( x 2 − x ‾ ) 2 + ⋯ + ( x k − x ‾ ) 2 k S^2=\frac{(x_1-\overline{x})^2+(x_2-\overline{x})^2+\cdots+(x_k-\overline{x})^2}{k} S2=k(x1−x)2+(x2−x)2+⋯+(xk−x)2，其中 x ‾ \overline{x} x为这 k k k个整数的平均值，即 x ‾ = x 1 + x 2 + ⋯ + x k k \overline{x}=\frac{x_1+x_2+\cdots+x_k}{k} x=kx1+x2+⋯+xk。
输入格式
第一行输入
n
,
m
n,m
n,m
下面
n
n
n行，每行
m
m
m个数，第
i
i
i行第
j
j
j列为
h
i
,
j
h_{i,j}
hi,j
输出格式
输出最小的方差乘 ( n + m − 1 ) 2 (n+m-1)^2 (n+m−1)2后的值
样例输入
2 2
1 2
3 4
样例输出
14
数据范围
对于
30
%
30\%
30%的数据，
1
≤
n
,
m
≤
10
1\leq n,m\leq 10
1≤n,m≤10
对于
50
%
50\%
50%的数据，
1
≤
n
,
m
≤
20
1\leq n,m\leq 20
1≤n,m≤20
对于
100
%
100\%
100%的数据，
1
≤
n
,
m
≤
50
,
0
≤
h
x
,
y
≤
50
1\leq n,m\leq 50,0\leq h_{x,y}\leq 50
1≤n,m≤50,0≤hx,y≤50
题解
可以看出要经过的点的数量为 n + m − 1 n+m-1 n+m−1，为方便表述，令 k = n + m − 1 k=n+m-1 k=n+m−1。
数据范围比较小，平均数又不好处理，我们可以考虑枚举平均数。因为 0 ≤ x ‾ ≤ 50 0\leq \overline{x} \leq 50 0≤x≤50，所以 0 ≤ k ⋅ x ‾ ≤ 50 k 0\leq k\cdot\overline{x} \leq 50k 0≤k⋅x≤50k，且 k ⋅ x ‾ k\cdot\overline{x} k⋅x为整数。于是我们就可以枚举 k ⋅ x ‾ k\cdot\overline{x} k⋅x，再计算最大值。
将要求的式子拆一下， k 2 × S 2 = k 2 × ( x 1 − x ‾ ) 2 + ( x 2 − x ‾ ) 2 + ⋯ + ( x k − x ‾ ) 2 k = k ( ( ∑ x i 2 ) − 2 x ‾ ( ∑ x i ) + k x ‾ 2 ) k^2\times S^2=k^2\times\frac{(x_1-\overline{x})^2+(x_2-\overline{x})^2+\cdots+(x_k-\overline{x})^2}{k}=k((\sum x_i^2)-2\overline{x}(\sum x_i)+k\overline{x}^2) k2×S2=k2×k(x1−x)2+(x2−x)2+⋯+(xk−x)2=k((∑xi2)−2x(∑xi)+kx2)，在 x ‾ \overline{x} x一定的情况下， x i x_i xi的贡献为 k ( x i 2 − 2 x ‾ x i ) = k x i 2 − 2 k x ‾ x i k(x_i^2-2\overline{x}x_i)=kx_i^2-2k\overline{x}x_i k(xi2−2xxi)=kxi2−2kxxi。
设当前枚举的
k
⋅
x
‾
k\cdot\overline{x}
k⋅x值为
t
t
t，设
f
i
,
j
f_{i,j}
fi,j表示从
(
1
,
1
)
(1,1)
(1,1)到
(
i
,
j
)
(i,j)
(i,j)的最小的贡献，则可以列出转移式
f
i
,
j
=
min
(
f
i
−
1
,
j
,
f
i
,
j
−
1
)
+
k
⋅
h
i
,
j
2
+
2
t
⋅
h
i
,
j
f_{i,j}=\min(f_{i-1,j},f_{i,j-1})+k\cdot h_{i,j}^2+2t\cdot h_{i,j}
fi,j=min(fi−1,j,fi,j−1)+k⋅hi,j2+2t⋅hi,j
那么答案为对于每一个 t t t中 f n , m + t 2 f_{n,m}+t^2 fn,m+t2的最小值。
那如果这 k k k个数的平均值乘 k k k与 t t t不相等怎么办，不就多算了几种情况吗？
会多一些情况，但不影响答案。设
t
=
k
x
‾
+
a
(
a
≠
0
)
t=k\overline{x}+a(a\neq0)
t=kx+a(a=0)，
此次计算的答案：
k
(
∑
x
i
2
)
−
2
t
(
∑
x
i
)
+
t
2
=
k
(
∑
x
i
2
)
−
2
(
k
x
‾
+
a
)
(
k
x
‾
)
+
(
k
x
‾
+
a
)
2
k(\sum x_i^2)-2t(\sum x_i)+t^2=k(\sum x_i^2)-2(k\overline{x}+a)(k\overline{x})+(k\overline{x}+a)^2
k(∑xi2)−2t(∑xi)+t2=k(∑xi2)−2(kx+a)(kx)+(kx+a)2
实际上的答案： k ( ∑ x i 2 ) − 2 k x ‾ ( ∑ x i ) + k 2 x ‾ 2 = k ( ∑ x i 2 ) − 2 ( k x ‾ ) 2 + k 2 x ‾ 2 k(\sum x_i^2)-2k\overline{x}(\sum x_i)+k^2\overline{x}^2=k(\sum x_i^2)-2(k\overline{x})^2+k^2\overline{x}^2 k(∑xi2)−2kx(∑xi)+k2x2=k(∑xi2)−2(kx)2+k2x2
上下做差得 − 2 a k x ‾ + 2 a k x ‾ + a 2 = a 2 > 0 -2ak\overline{x}+2ak\overline{x}+a^2=a^2>0 −2akx+2akx+a2=a2>0，所以当 t ≠ k x ‾ t\neq k\overline{x} t=kx时，得出的答案会更大，而这个答案的一定会被 t = k x ‾ t=k\overline{x} t=kx时的答案覆盖，所以这是可行的。
枚举 t t t是 O ( 50 ( n + m ) ) O(50(n+m)) O(50(n+m))，每次DP都是 O ( n m ) O(nm) O(nm)，所以总时间复杂度为 O ( 50 n m ( n + m ) ) O(50nm(n+m)) O(50nm(n+m))。
code
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long ans=1e18,a[55][55],f[55][55];
int main()
{
scanf("%d%d",&n,&m);k=n+m-1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%lld",&a[i][j]);
}
}
for(int o=0;o<=5000;o++){
f[1][1]=a[1][1]*a[1][1]*k-2*a[1][1]*o;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i!=1||j!=1) f[i][j]=1e18;
if(i>1) f[i][j]=min(f[i][j],f[i-1][j]+a[i][j]*a[i][j]*k-2*a[i][j]*o);
if(j>1) f[i][j]=min(f[i][j],f[i][j-1]+a[i][j]*a[i][j]*k-2*a[i][j]*o);
}
}
ans=min(ans,f[n][m]+o*o);
}
printf("%lld",ans);
return 0;
}