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;}
评论