2022-12-30:某天小美进入了一个迷宫探险,根据地图所示,这个迷宫里有无数个房间序号分别为1、2、3、...入口房间的序号
2023-02-26 09:49:38 时间
2022-12-30:某天小美进入了一个迷宫探险,根据地图所示,这个迷宫里有无数个房间
序号分别为1、2、3、...入口房间的序号为1
任意序号为正整数x的房间,都与序号 2*x 和 2*x + 1 的房间之间各有一条路径
但是这些路径是单向的,即只能从序号为x的房间去到序号为 2*x 或 2*x+1 的房间
而不能从 2*x 或 2*x+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;
}
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023