1.首先答案必定为A [ x 1 , y 1 ] + A [ x 2 , y 2 ] + C ∗ ( ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ ) A[x_1,y_1]+A[x_2,y_2]+C*(|x_1-x_2|+|y_1-y_2|)A[x1,y1]+A[x2,y2]+C∗(∣x1−x2∣+∣y1−y2∣)
2.我们想办法去掉绝对值，给选择的两个点规定方向，分别是一个点在左下，一个点右上；一点左上，一个点右下（方向是两个点的相对方向）。
1.当左下右上时，维护 m 1 [ i ] [ j ] m_1[i][j]m1[i][j] 为左下角到i , j i,ji,j的最小的 C ∗ ( i − j ) + A [ i , j ] C*(i-j)+A[i,j]C∗(i−j)+A[i,j]。
因为如果这个方案取到答案:
a n s = A [ x 1 , y 1 ] + A [ x 2 , y 2 ] + C ∗ ( y 2 − y 1 + x 1 − x 2 ) ( x 1 , y 1 左 下 ， x 2 , y 2 右 上 ) 。 ans=A[x_1,y_1]+A[x_2,y_2]+C*(y_2-y_1+x_1-x_2)(x_1,y_1左下，x_2,y_2右上)。ans=A[x1,y1]+A[x2,y2]+C∗(y2−y1+x1−x2)(x1,y1左下，x2,y2右上)。
变换得a n s = A [ x 2 , y 2 ] + C ∗ ( y 2 − x 2 ) + A [ x 1 , y 1 ] + C ( x 1 − y 1 ) ans=A[x_2,y_2]+C*(y_2-x_2)+A[x_1,y_1]+C(x_1-y_1)ans=A[x2,y2]+C∗(y2−x2)+A[x1,y1]+C(x1−y1),我们令m 1 [ i , j ] = A [ i , j ] + C ∗ ( i − j ) m_1[i,j]=A[i,j]+C*(i-j)m1[i,j]=A[i,j]+C∗(i−j),m 1 m_1m1维护最小值。
2.同理当左上右下时，维护 m 2 [ i ] [ j ] m_2[i][j]m2[i][j] 为左上角到i , j i,ji,j的最小的 − C ∗ ( i + j ) + A [ i , j ] -C*(i+j)+A[i,j]−C∗(i+j)+A[i,j]。
m 2 [ i , j ] = A [ i , j ] − C ∗ ( i + j ) m_2[i,j]=A[i,j]-C*(i+j)m2[i,j]=A[i,j]−C∗(i+j)。(想不明白画画图)。
维护利用了二维前缀和思想
代码如下
/********************************************************************* 程序名: 版权: Joecai 作者: Joecai 日期: 2022-04-28 23:56 说明: *********************************************************************/ #include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) #define ll long long #define endl "\n" #define LOCAL #define pb push_back #define int long long typedef pair<ll, ll> PII; #define eb emplace_back #define sp(i) setprecision(i) const int N = 1000 + 10, INF = 0x3f3f3f3f; int h, w, c; int a[N][N]; int m1[N][N];//维护左下角到i,j的的最小值 int m2[N][N];//维护左上角到i,j的最小值 void solve() { cin >> h >> w >> c; memset(m1, 0x3f, sizeof(m1)); memset(m2, 0x3f, sizeof(m2)); for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { cin >> a[i][j]; } } for (int i = h; i >= 1; i--) { for (int j = 1; j <= w; j++) { m1[i][j] = min({a[i][j] + c * (i - j), m1[i + 1][j], m1[i][j - 1]}); //左下到右上 } } for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { m2[i][j] = min({a[i][j] - c * (i + j), m2[i - 1][j], m2[i][j - 1]}); //左s上到右下 } } int ans = 0x3f3f3f3f3f3f3f3f; for (int i = h; i >= 1; i--) { for (int j = 1; j <= w; j++) { ans = min(ans, a[i][j] + c * (j - i) + min(m1[i + 1][j], m1[i][j - 1])); } } for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { ans = min(ans, a[i][j] + c * (i + j) + min(m2[i - 1][j], m2[i][j - 1])); } } cout << ans << endl; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; //cin>>__; while (__--) { solve(); } return 0; }
点个赞再走叭~(*σ´∀`)σ
