[code source] National Railway

2022.04.28

Topic link ： National railway - subject - Daimayuan Online Judge

Title Description

dls The competitive kingdom can be expressed as a kingdom with  HH Row sum  WW Column grid , We let  (i,j)(i,j) From the North  ii Line and from the West  jj Column grid . Recently, the citizens of this kingdom want the king to build a railway .

The construction of the railway is divided into two stages ：

1： Pick from all the grids 2 A different grid , Build a railway station on these two grids . The cost of building a railway station on a network is  Ai,j;

2： Build a rail between the two grids , Suppose the grid we choose is  (x1,y1) and (x2,y2), The price is  C∗(|x1−x2|+|y1−y2|);

dls My wish is to build a railway with the least cost for the benefit of citizens . Now please find out the minimum cost .

Topic input

On the first line, enter three integers to represent H,W,C

Next H That's ok , Each row W It's an integer , representative Ai,j

Topic output

Output an integer representing the minimum cost

Data range

2≤H,W≤1000

1≤C≤1e9

1≤Ai,j≤1e9

The sample input ：

3 4 2
1 7 7 9
9 6 3 7
7 8 6 4

Sample output ：

10 

  This question requires a minimum cost , That is, the cost of two sites + Railway cost （A(x1,y1)+A(x2,y2)+ C∗(|x1−x2|+|y1−y2|)). Consider removing the absolute value , It is transformed into the minimum cost problem corresponding to two points .

(x1,y1) , (x2,y2) There are two kinds of positional relationships ：

1.   x2>=x1 And y2>=y1 (x1!=x2&&y1!=y2)（ On the main diagonal ）

        cost : A(x1,y1)+A(x2,y2)+ C∗(|x1−x2|+|y1−y2|)

                =A(x1,y1)+A(x2,y2) + C∗(x2 − x1) + C*(y2 − y1)

                =A(x1,y1) - C ∗ (x1 + y1) + A(x2,y2) + C*(x2 + y2)

In two parts , Find the minimum value respectively

 

（ The picture is a little ugly , Make do with it ） 

  Consider enumeration （x2,y2） The location of , Satisfy x2>=x1 And y2>=y1 The points of the relationship are shaded in the figure , Ask quickly （x1,y1） Best location for , So how to use O（1） Complexity query （x1,y1） The best location for ？ Minimum value of two-dimensional prefix

2.  x1>=x2 And y2>=y1 (x1!=x2&&y1!=y2)（ On the sub diagonal ）

        cost : A(x1,y1)+A(x2,y2)+ C∗(|x1−x2|+|y1−y2|)

                =A(x1,y1)+A(x2,y2) + C∗(x1 − x2) + C*(y2 − y1)

                =A(x1,y1) + C ∗ (x1 - y1) + A(x2,y2) + C*(y2 - x2)

In two parts , Find the minimum value respectively

  ditto , Consider enumeration （x2,y2） The location of , Satisfy x1>=x2 And y2>=y1 The points of the relationship are shaded in the figure , Ask quickly （x1,y1） Best location for ,O（1） Complexity query （x1,y1） The best location for ？

Minimum value of two-dimensional prefix

Two dimensional prefixes and ： The sum of the values of each element of the rectangle .

Minimum value of two digit prefix ： The minimum value of each element in the rectangle .

Properties are similar to binary prefixes and , But it's different , The minimum value of two-dimensional prefix cannot be used to find the minimum value of any rectangular area , The starting point of the rectangle is fixed . This question just meets the requirements , Using the property of two-dimensional prefix minimum, the preprocessing is in O（1） Under the complexity of （x1,y1） Best location for .

So how to preprocess the minimum value of two-dimensional prefix ？

  Make f(i)(j) For （1,1） As a starting point （i,j） A rectangle with an end point .

  f（x,y） You can have the red area and yellow area in the figure transferred from , Therefore, the transfer equation can be obtained

                f (x , y) = min（ f(x,y-1) ,f(x-1)(y),a(x)(y) ）

See the code for details.

#include <bits/stdc++.h>
using namespace std;
#define int long long // Must open longlong, Not open longlong wa Three times , Adjust for half a day bug
int h, w, c, ans = 1e18;
int pre_min[1009][1009], pre_min2[1009][1009], a[1009][1009]; // pre_min It is the minimum prefix value of preprocessing in the first case ,pre_min2 For the second case 
signed main()
{
    scanf("%lld%lld%lld", &h, &w, &c);
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            scanf("%lld", &a[i][j]); // Input 
    // Situation 1 
    for (int i = 0; i <= h; i++)
        pre_min[i][0] = 1e18; // initialization ！ Be sure to drive a lot , because (i+j)*c Maximum attainable 2000*1e9！！！
    for (int i = 0; i <= w; i++)
        pre_min[0][i] = 1e18;
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            pre_min[i][j] = min(pre_min[i - 1][j], min(pre_min[i][j - 1], a[i][j] - c * (i + j))); // Minimum value of two-dimensional prefix 
    for (int i = 1; i <= h; i++) // enumeration （x2,y2）
        for (int j = 1; j <= w; j++)
            ans = min(ans, a[i][j] + c * (i + j) + min(pre_min[i - 1][j], pre_min[i][j - 1])); // Update minimum 
    // Situation two 
    for (int i = 0; i <= h; i++) // initialization 
        pre_min2[i][0] = 1e18;
    for (int i = 0; i <= w; i++)
        pre_min2[h + 1][i] = 1e18; // It's different here , The starting point of the minimum value of the two digit prefix is （h,1）
    for (int i = h; i >= 1; i--) // enumeration （x2,y2）
        for (int j = 1; j <= w; j++)
            pre_min2[i][j] = min(pre_min2[i + 1][j], min(pre_min2[i][j - 1], a[i][j] + c * (i - j))); // Minimum value of two-dimensional prefix 
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++)
            ans = min(ans, a[i][j] + c * (j - i) + min(pre_min2[i + 1][j], pre_min2[i][j - 1])); // Update minimum 
    cout << ans;
}