解题思路

外卖小哥在网格上只能向“右/下”移动，进入某格的代价为该格的值；此外可以至多使用 k 次无人机，将当前位置一次性“跳转”到任意代价不大的格子（grid[x][y] ≤ grid[i][j]），该次移动费用为 0。

把问题视作在有向图上求最短路：

• 普通边：从 (i,j) 到右/下邻居，边权为邻居的值；
• 无人机边：从 (i,j) 到任意 grid[x][y] ≤ grid[i][j]，边权为 0，最多使用 k 次。

直接建图会产生 O((mn)^2) 的零权边，无法承受。注意到无人机跳转只要求目的地值不大于出发地值，因此可以做“值域压缩 + DP”。

设 dp[t][i][j] 表示到达 (i,j)，至多使用 t 次无人机的最小代价。转移有两类：

1. 常规移动： dp[t][i][j] = min(dp[t][i-1][j], dp[t][i][j-1]) + grid[i][j]

2. 使用一架无人机直接落到 (i,j)： 从任意代价 ≥ grid[i][j] 的格子跳来都行，且不再加代价。 令所有格子值做降序坐标压缩，记 rank(i,j) 为 (i,j) 的值在压缩序中的下标（值越大 rank 越小）。 对固定 t-1，我们预处理 best_ge[r] = 所有 rank ≤ r 的格子中 dp[t-1] 的最小值， 则“无人机”转移为 dp[t][i][j] = min(dp[t][i][j], best_ge[ rank(i,j) ])。

这样，每一层 t 只需：

• 先用上一层 dp[t-1] 按值域做一次“前缀最小”（降序前缀），得到 best_ge；
• 再按行从左到右、从上到下做一次普通网格 DP，并与 best_ge 取最小。

初值：dp[0][0][0] = 0，其余根据右/下最短路径递推得到；答案为 dp[k][m-1][n-1]。

该方法本质是多阶段动态规划 + 值域压缩 + 前缀最小，把“任意到不大于值”的零权多源跳跃压缩成 O(1) 查询。

复杂度分析

• 预处理/每层 DP：统计每个值的最小 dp 并做一次前缀最小 O(mn)；常规网格转移 O(mn)。
• 总时间复杂度：O(k · m · n)
• 空间复杂度：O(m · n)（两层 dp 滚动 + 若干一维辅助数组）

在 m,n ≤ 100、k 适中时完全可行。

代码实现

Python

import sys
from ast import literal_eval

INF = 10**18

def min_cost_with_drones(grid, k):
    m, n = len(grid), len(grid[0])

    # 值域压缩（降序，值越大 rank 越小）
    vals = sorted({grid[i][j] for i in range(m) for j in range(n)}, reverse=True)
    rank_map = {v: idx for idx, v in enumerate(vals)}
    rk = [[rank_map[grid[i][j]] for j in range(n)] for i in range(m)]
    R = len(vals)

    # dp0：不使用无人机的普通右/下最小路径
    dp_prev = [[INF] * n for _ in range(m)]
    dp_prev[0][0] = 0
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            best = INF
            if i > 0: best = min(best, dp_prev[i-1][j])
            if j > 0: best = min(best, dp_prev[i][j-1])
            dp_prev[i][j] = best + grid[i][j]

    # 逐层增加无人机次数
    for _ in range(k):
        # 统计每个 rank 的最小 dp_prev
        best_exact = [INF] * R
        for i in range(m):
            for j in range(n):
                r = rk[i][j]
                if dp_prev[i][j] < best_exact[r]:
                    best_exact[r] = dp_prev[i][j]
        # 降序前缀最小：best_ge[r] = 所有 rank<=r 的最小值
        best_ge = [INF] * R
        cur = INF
        for r in range(R):
            cur = min(cur, best_exact[r])
            best_ge[r] = cur

        # 本层 dp
        dp_now = [[INF] * n for _ in range(m)]
        dp_now[0][0] = 0  # 起点代价为0
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                # 常规右/下
                best = INF
                if i > 0: best = min(best, dp_now[i-1][j])
                if j > 0: best = min(best, dp_now[i][j-1])
                cand = best + grid[i][j]
                # 使用一架无人机直接落到 (i,j)
                cand = min(cand, best_ge[rk[i][j]])
                dp_now[i][j] = cand
        dp_prev = dp_now

    return dp_prev[m-1][n-1]

def main():
    data = sys.stdin.read().strip().splitlines()
    m, n, k = map(int, data[0].split())
    grid = []
    for i in range(1, 1 + m):
        line = data[i].strip()
        row = list(map(int, line.split()))
        grid.append(row)
    print(min_cost_with_drones(grid, k))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

/** ACM 风格主类名为 Main */
public class Main {
    static final long INF = (long)1e18;

    static long solve(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;

        // 值域压缩（降序）
        ArrayList<Integer> vs = new ArrayList<>();
        for (int[] ints : grid)
            for (int v : ints) vs.add(v);
        Collections.sort(vs, Collections.reverseOrder());
        ArrayList<Integer> uniq = new ArrayList<>();
        for (int v : vs) {
            if (uniq.isEmpty() || !uniq.get(uniq.size()-1).equals(v))
                uniq.add(v);
        }
        int R = uniq.size();
        HashMap<Integer, Integer> rankMap = new HashMap<>();
        for (int i = 0; i < R; i++) rankMap.put(uniq.get(i), i);
        int[][] rk = new int[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                rk[i][j] = rankMap.get(grid[i][j]);

        // dp0：常规右/下
        long[][] dpPrev = new long[m][n];
        for (long[] row : dpPrev) Arrays.fill(row, INF);
        dpPrev[0][0] = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                long best = INF;
                if (i > 0) best = Math.min(best, dpPrev[i-1][j]);
                if (j > 0) best = Math.min(best, dpPrev[i][j-1]);
                dpPrev[i][j] = best + grid[i][j];
            }
        }

        for (int t = 0; t < k; t++) {
            long[] bestExact = new long[R];
            Arrays.fill(bestExact, INF);
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++) {
                    int r = rk[i][j];
                    if (dpPrev[i][j] < bestExact[r]) bestExact[r] = dpPrev[i][j];
                }
            long[] bestGe = new long[R];
            long cur = INF;
            for (int r = 0; r < R; r++) {
                cur = Math.min(cur, bestExact[r]);
                bestGe[r] = cur;
            }

            long[][] dpNow = new long[m][n];
            for (long[] row : dpNow) Arrays.fill(row, INF);
            dpNow[0][0] = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0 && j == 0) continue;
                    long best = INF;
                    if (i > 0) best = Math.min(best, dpNow[i-1][j]);
                    if (j > 0) best = Math.min(best, dpNow[i][j-1]);
                    long cand = best + grid[i][j];
                    cand = Math.min(cand, bestGe[rk[i][j]]);
                    dpNow[i][j] = cand;
                }
            }
            dpPrev = dpNow;
        }
        return dpPrev[m-1][n-1];
    }

    static int[][] readGrid(BufferedReader br, int m, int n) throws Exception {
        int[][] g = new int[m][n];
        for (int i = 0; i < m; i++) {
            String line = br.readLine();
            String[] parts = line.trim().replaceAll("\\s+", " ").split(" ");
            for (int j = 0; j < n; j++) g[i][j] = Integer.parseInt(parts[j]);
        }
        return g;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().trim().split("\\s+");
        int m = Integer.parseInt(first[0]);
        int n = Integer.parseInt(first[1]);
        int k = Integer.parseInt(first[2]);
        int[][] grid = readGrid(br, m, n);
        System.out.println(solve(grid, k));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = (long long)1e18;

long long solve(const vector<vector<long long>>& grid, int k) {
    int m = (int)grid.size(), n = (int)grid[0].size();

    // 值域压缩（降序）
    vector<long long> vals;
    vals.reserve(m * n);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            vals.push_back(grid[i][j]);
    sort(vals.begin(), vals.end(), greater<long long>());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int R = (int)vals.size();
    unordered_map<long long,int> rankMap;
    rankMap.reserve(vals.size()*2);
    for (int i = 0; i < R; ++i) rankMap[vals[i]] = i;

    vector<vector<int>> rk(m, vector<int>(n, 0));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            rk[i][j] = rankMap[grid[i][j]];

    // dp0：常规右/下
    vector<vector<long long>> dpPrev(m, vector<long long>(n, INF));
    dpPrev[0][0] = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == 0 && j == 0) continue;
            long long best = INF;
            if (i > 0) best = min(best, dpPrev[i-1][j]);
            if (j > 0) best = min(best, dpPrev[i][j-1]);
            dpPrev[i][j] = best + grid[i][j];
        }
    }

    for (int t = 0; t < k; ++t) {
        vector<long long> bestExact(R, INF);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                int r = rk[i][j];
                bestExact[r] = min(bestExact[r], dpPrev[i][j]);
            }
        vector<long long> bestGe(R, INF);
        long long cur = INF;
        for (int r = 0; r < R; ++r) {
            cur = min(cur, bestExact[r]);
            bestGe[r] = cur;
        }

        vector<vector<long long>> dpNow(m, vector<long long>(n, INF));
        dpNow[0][0] = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) continue;
                long long best = INF;
                if (i > 0) best = min(best, dpNow[i-1][j]);
                if (j > 0) best = min(best, dpNow[i][j-1]);
                long long cand = best + grid[i][j];
                cand = min(cand, bestGe[rk[i][j]]);
                dpNow[i][j] = cand;
            }
        }
        dpPrev.swap(dpNow);
    }
    return dpPrev[m-1][n-1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n, k;
    if (!(cin >> m >> n >> k)) return 0;
    vector<vector<long long>> grid(m, vector<long long>(n, 0));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> grid[i][j];
    cout << solve(grid, k) << "\n";
    return 0;
}

题目内容

给定一个$m×n$的二维数组$grid$表示地图，数组每个值代表该点的通行成本，给定$k$表示可以使用无人机配送次数。

现有一个外卖小哥，从$(0，0)$位置出发，要送餐到$(m-1,n-1)$位置，有两种方式可以配送:

$1.$按规则配送:可以从当前区域向右或向下一格，配送成本为目标点的通行成本;

$2.$无人机配送:可从任意区域(i,j)调用无人机将餐品送到任意通行成本不大于$(i,j)$ 的区域$(x,y)$，即$grid[x][y] <= grid[i][j]$，此方式配送成本为$0$，但至多使用$k$次。

请你计算返回最小总配送成本

输入描述

第一行输入三个整数，表示$m,n,k$

以后$m$行每行$n$个整数，表示$grid$

输出描述

输出一个整数表示最小总配送成本

样例1

输入

3 4 2
1 2 5 7
9 5 6 7
7 5 7 5

输出

7

提示

$1 <= k <= n <= 100$

$n = grid[i].length$

$0 <= grid[i][j]<= 10^9$