题意翻译

给出一个 $n \times m$ 的矩阵，每个矩阵的权值代表该点的初始高度。

现在需要从点 $( 1 , 1 )$ 走到点 $( n , m )$ ，每一步需要满足以下条件：

只能向右或向下
设当前格子的高度为 $x$ ，只能移动到高度为 $x + 1$ 的格子上去

初始时可以进行操作，使得某个格子的高度减少一个单位。

问最少需要进行多少次操作，可以存在至少一条从点 $( 1 , 1 )$ 到点 $( n , m )$ 的路线

输入格式

第一行包含一个整数 $t$ ，表示数据组数

其中，每一组数据的第一行包含两个整数 $n , m$ ，表示矩阵的行数与列数

之后是一个 $n \times m$ 的矩阵，表示初始状态下矩阵中每个点的高度

输出格式

对于每组数据，输出一行一个整数，表示最少的操作次数

Input & Output 's examples

Input 's eg

5
3 4
1 2 3 4
5 6 7 8
9 10 11 12
5 5
2 5 4 8 3
9 10 11 5 1
12 8 4 2 5
2 2 5 4 1
6 8 2 4 2
2 2
100 10
10 1
1 2
123456789876543 987654321234567
1 1
42

Output 's eg

9
49
111
864197531358023
0

数据范围和约定

对于 $100\%$ 的数据，保证 $1 \leq t \leq 100$ , $1 \leq n , m \leq 100$ , $1 \leq a_{i , j} \leq 10^15$

分析

很套路的 $\text{dp}$ 题，但也有一定难度，放在 $\text{Div 3}$ 的 $\text{F}$ 题完全可以接受

读完题后，很容易想到此题的一个弱化版本：给定一个矩阵，每次只可以向下或向右移动，如何行走才能使得经过点的点权之和最大？

思考如何把这个题转化过去。不难发现，如果知道了这个点的起点高度 $h$ ，则走到坐标为 $(i , j)$ 的点上高度应该为 $h + i + j$ 。

所以就有了以下两点推论：

设一个点坐标为 $(i , j)$ ，若 $a[i][j] > h + i + j$ ，则该点不可能被经过。
若 $a[i][j] \leq h + i + j$ ，则经过该点所需要的操作次数为 $(h + i + j) - a[i][j]$ 。

也就是说，我们只需要把 $a[i][j] \leq h$ 的点的点权设为 $(h + i + j) - a[i][j]$ 即可。

然后考虑如何解决上面的弱化版问题。

设 $f[i][j]$ 表示从 $(1 , 1)$ 走到 $(i , j)$ 所需要的最少次数，则 $f[1][1] = 0$ 。

之后考虑如何转移。首先，对于点 $(i , j)$ ，有

$f[i][j] = f[i][j] + (h + i + j - a[i][j])$

之后考虑向外拓展。若 $i + 1 \leq n$ ，则

$f[i + 1][j] = min(f[i + 1][j] , f[i][j])$

$j$ 也同理，若 $j + 1 \leq m$ ，则

$f[i][j + 1] = min(f[i][j + 1] , f[i][j])$

最后在外面套一层 $O(n^2)$ 的枚举，枚举矩阵元素并倒推初始点的权值，即 $h = a[i][j] - i - j$ 。

每一次 $\text{dp}$ 的时间复杂度为 $O(n^2)$ ，加上外层的枚举，时间复杂度为 $O(n^4)$ 。足以跑过 $100\%$ 的数据。

剩下的见代码即可。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;
const int INF = 2147483647;
const long long INFL = 9023372036854775801;

ll a[101][101] , f[101][101];

ll solve(ll n , ll m , ll sta){
    rep(i , 1 , n){
        rep(j , 1 , m){
            f[i][j] = INFL;
        }
    }
    f[1][1] = 0;
    rep(i , 1 , n){
        rep(j , 1 , m){
            ll val = i + j + sta;
            if(val > a[i][j]){
                f[i][j] = INFL;
                continue;
            }
            f[i][j] += a[i][j] - val;
            if(i + 1 <= n){
                f[i + 1][j] = min(f[i + 1][j] , f[i][j]);
            }
            if(j + 1 <= m){
                f[i][j + 1] = min(f[i][j + 1] , f[i][j]);
            }
        }
    }
    return f[n][m];
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    ll t , n , m;
    scanf("%lld" , &t);
    while(t --){
        clean(a , 0);
        scanf("%lld%lld" , &n , &m);
        rep(i , 1 , n){
            rep(j , 1 , m){
                scanf("%lld" , &a[i][j]);
            }
        }
        ll ans = INFL;
        rep(i , 1 , n){
            rep(j , 1 , m){
                ans = min(ans , solve(n , m , a[i][j] - i - j));
            }
        }
        printf("%lld\n" , ans);
    }


    return 0;
}

【Codeforces】Decreasing Heights-题解