2022-12-30：某天小美进入了一个迷宫探险，根据地图所示，这个迷宫里有无数个房间 序号分别为1、2、3、...入口房间的序号为1 任意序号为正整数x的房间，都与序号 2*x 和 2*x + 1

2022-12-30：某天小美进入了一个迷宫探险，根据地图所示，这个迷宫里有无数个房间
序号分别为1、2、3、…入口房间的序号为1
任意序号为正整数x的房间，都与序号 2x 和 2x + 1 的房间之间各有一条路径
但是这些路径是单向的，即只能从序号为x的房间去到序号为 2x 或 2x+1 的房间
而不能从 2x 或 2x+1 的房间去到序号为x的房间
在任何时刻小美都可以选择结束探险并离开迷宫，但是离开之后将无法再次进入迷宫
小美还提前了解了迷宫中宝藏的信息
已知宝藏共有n个，其中第i个宝藏在序号为pi的房间，价值为wi
且一个房间中可能有多个宝藏
小美为了得到更多的宝藏，需要精心规划路线，她找到你帮忙
想请你帮她计算一下，能获得的宝藏价值和最大值为多少
第一行一个正整数n，表示宝藏数量。
第二行为n个正整数p1, p2,… pn，其中pi表示第 i 个宝藏在序号为pi的房间。
第三行为n个正整数w1, w2,… wn，其中wi表示第i个宝藏的价值为wi。
1 <= n <= 40000, 1 <= pi < 2^30, 1 <= wi <= 10^6。
来自美团。

答案2022-12-30：

动态规划，利用图来优化枚举。
时间复杂度：O(N)。
空间复杂度：O(N)。

代码用rust编写。代码如下：

use rand::Rng;

use std::collections::HashMap;

use std::iter::repeat;

fn main() {

    let nn: i32 = 100;

    let pp: i32 = 5000;

    let ww: i32 = 5000;

    let test_time: i32 = 5000;

    println!("测试开始");

    for i in 0..test_time {

        let n: i32 = rand::thread_rng().gen_range(0, nn) + 1;

        let mut p = random_array(n, pp);

        let mut w = random_array(n, ww);

        let ans1 = max_money1(n, &mut p, &mut w);

        let ans2 = max_money2(n, &mut p, &mut w);

        if ans1 != ans2 {

            println!("出错了!");

            println!("i = {}", i);

            println!("ans1 = {:?}", ans1);

            println!("ans2 = {:?}", ans2);

            break;

        }

    }

    println!("测试结束");

}

// 为了测试

// 普通动态规划

fn max_money1(n: i32, p: &mut Vec<i32>, w: &mut Vec<i32>) -> i32 {

    let mut rooms: Vec<Vec<i32>> = repeat(repeat(0).take(2).collect())

        .take(n as usize)

        .collect();

    for i in 0..n {

        rooms[i as usize][0] = p[i as usize];

        rooms[i as usize][1] = w[i as usize];

    }

    rooms.sort_by(|a, b| a[0].cmp(&b[0]));

    let mut ans = 0;

    let mut dp: Vec<i32> = repeat(-1).take(n as usize).collect();

    for i in 0..n {

        ans = get_max(ans, process1(i, &mut rooms, n, &mut dp));

    }

    return ans;

}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {

    if a > b {

        a

    } else {

        b

    }

}

fn process1(index: i32, rooms: &mut Vec<Vec<i32>>, n: i32, dp: &mut Vec<i32>) -> i32 {

    if dp[index as usize] != -1 {

        return dp[index as usize];

    }

    let mut next = 0;

    for i in index + 1..n {

        if reach(rooms[index as usize][0], rooms[i as usize][0]) {

            next = get_max(next, process1(i, rooms, n, dp));

        }

    }

    let mut ans = rooms[index as usize][1] + next;

    dp[index as usize] = ans;

    return dp[index as usize];

}

fn reach(from: i32, mut to: i32) -> bool {

    while to >= from {

        if from == to {

            return true;

        } else {

            to /= 2;

        }

    }

    return false;

}

// 正式方法

// 时间复杂度O(N)的动态规划

// 利用图来优化枚举

fn max_money2(n: i32, p: &mut Vec<i32>, w: &mut Vec<i32>) -> i32 {

    let mut rooms: Vec<Vec<i32>> = repeat(repeat(0).take(2).collect())

        .take(n as usize)

        .collect();

    for i in 0..n {

        rooms[i as usize][0] = p[i as usize];

        rooms[i as usize][1] = w[i as usize];

    }

    rooms.sort_by(|a, b| a[0].cmp(&b[0]));

    let mut first: HashMap<i32, i32> = HashMap::new();

    let mut graph: Vec<Vec<i32>> = vec![];

    for i in 0..n {

        let mut to = rooms[i as usize][0];

        while to > 0 {

            if first.contains_key(&to) {

                graph[*first.get(&to).unwrap() as usize].push(i);

                break;

            } else {

                to >>= 1;

            }

        }

        graph.push(vec![]);

        if !first.contains_key(&rooms[i as usize][0]) {

            first.insert(rooms[i as usize][0], i);

        }

    }

    let mut ans = 0;

    let mut dp: Vec<i32> = repeat(0).take(n as usize).collect();

    let mut i = n - 1;

    while i >= 0 {

        let mut post = 0;

        for next in graph[i as usize].iter() {

            if rooms[*next as usize][0] == rooms[i as usize][0] {

                dp[i as usize] += dp[*next as usize];

            } else {

                post = get_max(post, dp[*next as usize]);

            }

        }

        dp[i as usize] += post + rooms[i as usize][1];

        ans = get_max(ans, dp[i as usize]);

        i -= 1;

    }

    return ans;

}

// 为了测试

fn random_array(n: i32, v: i32) -> Vec<i32> {

    let mut arr: Vec<i32> = vec![];

    for _i in 0..n {

        arr.push(rand::thread_rng().gen_range(0, v) + 1);

    }

    return arr;

}

2022-12-30：某天小美进入了一个迷宫探险，根据地图所示，这个迷宫里有无数个房间 序号分别为1、2、3、...入口房间的序号为1 任意序号为正整数x的房间，都与序号 2*x 和 2*x + 1的相关教程结束。