小红书博主旅游攻略算法：寻找最大价值路线

小红是小红书的一个博主，她有很多的粉丝，有一些粉丝想让小红出一篇上尾市的旅游攻略。上尾市有 n 个景点，有 m 条路线，每个景点的攻略价值是 a ，要花费 h 时间浏览，不同景点之间的交通时间为 w。小红最多会选择3个相邻的景点，然后按顺序将景点写进攻略，她需要保证每个景点的浏览时间加上景点之间的交通时间总和不超过 k ，并且使得攻略的价值尽可能大，即景点的总价值尽可能大。求小红的攻略的最大价值.

Java8

输入描述第一行输入三个整数 n,m，k，含义如题目描述所示。第二行输入 n个整表示数组 a。第三行输入 n 个整数表示数组 h。接下来 m 行，每行输入三个整数 u,v,w表示景点 u,v 之间的交通时间为 w

输出描述输出一个整数表示答案内容：思路：

首先，我们需要建立一个二维数组dp，dp[i][j]表示在前i个景点中选择不超过j个相邻景点的情况下的最大攻略价值。
初始化dp数组，dp[0][0] = 0，表示没有选择任何景点时的攻略价值为0。
遍历每个景点i，计算dp[i][j]的值：
- 如果j=0，表示不选择相邻景点，此时dp[i][j] = max(dp[i-1][j] + a[i-1], dp[i-1][j+1] + a[i-1])，即选择当前景点或者不选择当前景点的最大攻略价值。
- 如果j=1，表示选择一个相邻景点，此时dp[i][j] = max(dp[i-1][j-1] + a[i-1], dp[i-1][j] + a[i-1])，即选择当前景点或者不选择当前景点的最大攻略价值。
- 如果j=2，表示选择两个相邻景点，此时dp[i][j] = dp[i-1][j-1] + a[i-1]，即选择当前景点的最大攻略价值。
最终的答案为dp[n][0]、dp[n][1]和dp[n][2]中的最大值。

Java代码实现如下：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            h[i] = scanner.nextInt();
        }
        int[][] w = new int[n][n];
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int t = scanner.nextInt();
            w[u - 1][v - 1] = t;
            w[v - 1][u - 1] = t;
        }

        int[][] dp = new int[n + 1][3];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 2; j++) {
                dp[i][j] = Integer.MIN_VALUE;
                // 不选择相邻景点
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + a[i - 1]);
                if (j >= 1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + a[i - 1]);
                }
                if (j >= 2) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 2] + a[i - 1]);
                }
            }
        }

        int maxScore = 0;
        for (int i = 0; i <= 2; i++) {
            maxScore = Math.max(maxScore, dp[n][i]);
        }
        System.out.println(maxScore);
    }
}

时间复杂度分析：由于需要遍历每个景点和每个相邻景点的情况，所以时间复杂度为O(n^2)。