小红书博主旅游攻略算法：上尾市景点价值最大化

小红是小红书的一个博主，她有很多的粉丝，有一些粉丝想让小红出一篇上尾市的旅游攻略。

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

输入描述

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

输出描述

输出一个整数表示答案

解法思路：

先构建一个邻接矩阵graph，表示每个景点之间的交通时间。
创建一个二维数组dp，dp[i][j]表示在选择第i个景点，并且攻略中最后一个景点是第j个景点的情况下，攻略的最大价值。
初始化dp数组，将dp[0][j]设置为第一个景点的攻略价值a[0]。
从第二个景点开始，遍历每个景点i，以及前一个景点j，计算dp[i][j]的值。
- 对于每个i，遍历前一个景点j，找到满足条件的dp[i][j]的最大值。
- dp[i][j]的最大值为dp[j][k] + a[i]，其中k可以是j的前一个景点，或者再前一个景点。
- 同时，需要保证dp[j][k] + a[i]的值加上从景点k到景点i的交通时间和浏览时间不超过k。
最后，在dp数组的最后一行找到最大值，即为答案。

代码实现如下：

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[][] graph = new int[n][n];
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            int w = scanner.nextInt();
            graph[u][v] = w;
            graph[v][u] = w;
        }

        int[][] dp = new int[n][n];
        dp[0][0] = a[0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Integer.MIN_VALUE;
                for (int k1 = 0; k1 < n; k1++) {
                    if (j == k1) continue;
                    for (int k2 = 0; k2 < n; k2++) {
                        if (j == k2 || k1 == k2) continue;
                        if (dp[j][k1] != Integer.MIN_VALUE) {
                            int time = h[i] + graph[k1][j] + graph[k2][j];
                            if (time <= k) {
                                dp[i][j] = Math.max(dp[i][j], dp[j][k1] + a[i]);
                            }
                        }
                    }
                }
            }
        }

        int max = Integer.MIN_VALUE;
        for (int j = 0; j < n; j++) {
            for (int k1 = 0; k1 < n; k1++) {
                if (j == k1) continue;
                for (int k2 = 0; k2 < n; k2++) {
                    if (j == k2 || k1 == k2) continue;
                    max = Math.max(max, dp[j][k1]);
                }
            }
        }

        System.out.println(max);
    }
}

复杂度分析：

时间复杂度：O(n^4)，其中n为景点的数量。需要遍历dp数组，时间复杂度为O(n^3)。同时，构建邻接矩阵graph的时间复杂度为O(m)，m为路线的数量。总时间复杂度为O(n^4 + m)。
空间复杂度：O(n^2)，需要使用dp数组和graph数组，空间复杂度为O(n^2)。