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

思路：

1. 创建一个二维数组dp，dp[i][j]表示选择前i个景点，浏览时间和不超过j的情况下的最大价值。
2. 初始化dp数组，dp[0][j]表示选择0个景点，浏览时间和不超过j，即为0。
3. 遍历每个景点i，更新dp[i][j]的值。
   • 如果选择第i个景点，浏览时间加上该景点的浏览时间h[i]不超过j，则dp[i][j]的值为dp[i-1][j-h[i]]+a[i]。
   • 如果选择第i个景点，浏览时间加上该景点的浏览时间h[i]超过j，则dp[i][j]的值为dp[i-1][j]。
   • 如果不选择第i个景点，则dp[i][j]的值为dp[i-1][j]。
4. 遍历整个dp数组，找到最大的值即为答案。

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[][] dp = new int[n+1][k+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= h[i-1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-h[i-1]] + a[i-1]);
                }
            }
        }
        
        int max = 0;
        for (int i = 0; i <= k; i++) {
            max = Math.max(max, dp[n][i]);
        }
        
        System.out.println(max);
    }
}

复杂度分析：

• 时间复杂度为O(n*k)，其中n为景点数量，k为浏览时间上限。
• 空间复杂度为O(n*k)