解题思路

本题是一个典型的动态规划问题。忍者的目标是从第一排或第二排的房间 1 出发，到达第一排或第二排的房间 n，要求最小化消耗的时间。根据题意，我们可以从每个房间选择不同的路径（在两个房间之间跳跃或在同一排内移动），每种路径都有不同的消耗时间。我们需要通过动态规划来计算从起点到终点的最短时间。

动态规划状态定义

我们可以定义动态规划的状态如下：

• dp1[i] 表示从第一排的房间 i 出发，到达第 i 个房间所需的最小时间。
• dp2[i] 表示从第二排的房间 i 出发，到达第 i 个房间所需的最小时间。

接下来，我们根据题目给出的条件，来递推计算每个房间的最小花费。

状态转移方程

1. 同一排内的转移

• 从第一排房间 i 到房间 i+1 的消耗时间为 |a[i] - a[i+1]|。
• 从第二排房间 i 到房间 i+1 的消耗时间为 |b[i] - b[i+1]|。

2. 跨排的转移

• 从第一排房间 i 到第二排房间 i 的消耗时间为 2 * |a[i] - b[i]|。
• 从第二排房间 i 到第一排房间 i 的消耗时间为 2 * |b[i] - a[i]|。
• 从第一排房间 i 到第二排房间 i+1 的消耗时间为 3 * |a[i] - b[i+1]|。
• 从第二排房间 i 到第一排房间 i+1 的消耗时间为 3 * |b[i] - a[i+1]|。

初始状态

• 起点可以是第一排或第二排的房间 1。因此：
  • dp1[1] = 0
  • dp2[1] = 0

递推计算

从房间 1 出发，逐步计算每个房间的最小时间，最终得到到达房间 n 的最小时间。

时间复杂度分析

每个状态的计算只依赖于前一个状态，因此动态规划的复杂度是 O(n)，其中 n 是房间的数量。

代码实现

Python 代码

def main():
    n = int(input())

    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    dp1 = [0] * n
    dp2 = [0] * n

    dp1[0] = 0
    dp2[0] = 0

    for i in range(1, n):
        dp1[i] = min(dp1[i - 1] + abs(a[i] - a[i - 1]),
                      dp2[i - 1] + 3 * abs(b[i - 1] - a[i]))

        dp2[i] = min(dp2[i - 1] + abs(b[i] - b[i - 1]),
                      dp1[i - 1] + 3 * abs(a[i - 1] - b[i]))

        dp1[i] = min(dp1[i], dp2[i] + 2 * abs(a[i] - b[i]))
        dp2[i] = min(dp2[i], dp1[i] + 2 * abs(a[i] - b[i]))

    print(min(dp1[n - 1], dp2[n - 1]))

if __name__ == "__main__":
    main()

Java 代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a = new int[n];
        int[] b = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }

        long[] dp1 = new long[n];
        long[] dp2 = new long[n];

        dp1[0] = 0;
        dp2[0] = 0;

        for (int i = 1; i < n; i++) {
            dp1[i] = Math.min(dp1[i - 1] + Math.abs(a[i] - a[i - 1]),
                              dp2[i - 1] + 3 * (long)Math.abs(b[i - 1] - a[i]));

            dp2[i] = Math.min(dp2[i - 1] + Math.abs(b[i] - b[i - 1]),
                              dp1[i - 1] + 3 * (long)Math.abs(a[i - 1] - b[i]));

            dp1[i] = Math.min(dp1[i], dp2[i] + 2 * (long)Math.abs(a[i] - b[i]));
            dp2[i] = Math.min(dp2[i], dp1[i] + 2 * (long)Math.abs(a[i] - b[i]));
        }

        System.out.println(Math.min(dp1[n - 1], dp2[n - 1]));

        sc.close();
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    // 动态规划数组，使用 long long 防止溢出
    vector<long long> dp1(n), dp2(n);

    // 初始化
    dp1[0] = 0;
    dp2[0] = 0;

    // 动态规划转移
    for (int i = 1; i < n; i++) {
        dp1[i] = min({dp1[i - 1] + abs(a[i] - a[i - 1]),
                      dp2[i - 1] + 3LL * abs(b[i - 1] - a[i])
                     }); // 乘以 3 使用 long long

        dp2[i] = min({dp2[i - 1] + abs(b[i] - b[i - 1]),
                      dp1[i - 1] + 3LL * abs(a[i - 1] - b[i])
                     }); // 乘以 3 使用 long long
        dp1[i] = min(dp1[i], dp2[i] + 2LL * abs(a[i] - b[i]));
        dp2[i] = min(dp2[i], dp1[i] + 2LL * abs(a[i] - b[i]));
    }

    // 输出最小时间
    cout << min(dp1[n - 1], dp2[n - 1]) << endl;

    return 0;
}

题目内容

忍者在练习飞檐走壁。现在有两排房子。从左往右排列各有 $n$ 间。如下图。在每个房间的房顶。他有 $6$ 个选择:

第一排：$1$ $2$ $3$ ... $n$

第二排：$1$ $2$ $3$ ... $n$

1:从第一排房间 $i$ 到第一排的房间 $i+1$ 。消耗时间为两个房间的高度差。

2:从第二排房间 $i$ 到第二排的房间 $i+1$ 。消耗时间为两个房间的高度差。

3:从第一排房间 $i$ 到第二排的房间 $i$ 。消耗时间为两个房间的高度差 $*$ $2$ 。

4:从第二排房间 $i$ 到第一排的房间 $i$ 。消耗时间为两个房间的高度差 $*$ $2$ 。

5:从第一排房间 $i$ 到第二排的房间 $i+1$ 。消耗时间为两个房间的高度差 $*$ $3$ 。

6:从第二排房间 $i$ 到第一排的房间 $i+1$ 。消耗时间为两个房间的高度差 $*$ $3$ 。

注意:高度差应该是两个房间的高度的差的绝对值。

他希望花费最少的时间从第一排或第二排的房间 $1$ 开始，到达第一排或者第二排的房间 $n$ 。

请你求一下需要花费最少的时间是多少。

输入描述

一行：$n$ (每排的房子数，$1＜＝n＜＝10^5$)

一行：$a[1],a[2],...,a[n](1＜＝a[i]＜＝10^9)$

一行：$b[1],b[2],...,b[n](1＜＝b[i]＜＝10^9)$

输出描述

一个整数。需要花费的最少的时间。

样例1

输入

5
1 10 20 30 40
2 5 20 50 31

输出

31