题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
use std::io::{self, *}; use std::collections::HashMap; struct Item { v: usize, p: usize, q: usize, } fn main() { let stdin = io::stdin(); let mut line = String::new(); stdin.read_line(&mut line); let mut ns = line.trim().split(" "); let m = ns.next().unwrap().parse::<usize>().unwrap(); let n = ns.next().unwrap().parse::<usize>().unwrap(); let mut qs: HashMap<usize, Vec<usize>> = HashMap::new(); let mut items: Vec<Vec<Item>> = Vec::new(); for i in 0..n { line.clear(); stdin.read_line(&mut line); let mut ns = line.trim().split(" "); let mut item = Item { v: ns.next().unwrap().parse::<usize>().unwrap(), p: ns.next().unwrap().parse::<usize>().unwrap(), q: ns.next().unwrap().parse::<usize>().unwrap() }; item.p = item.v * item.p; // 记录一个主件,附件后续加入 items.push(vec![item]); // 记录附件指定主件索引的hashmap if items.last().unwrap()[0].q != 0 { qs.entry(items.last().unwrap()[0].q - 1).and_modify(|j| (*j).push(i)).or_insert(vec!(i)); } } // 把附件合并主件记录在主件a的vec中[a, a+b, a+c, a+b+c] for (k, v) in &qs { let sitems0 = &items[v[0]]; let pitems = &items[*k]; let pitem = &pitems[0]; let item = Item { v: sitems0[0].v + pitem.v, p: sitems0[0].p + pitem.p, q: 0 }; if v.len() > 1 { let sitems1 = &items[v[1]]; let item1 = Item { v: sitems1[0].v + item.v, p: sitems1[0].p + item.p, q: 0 }; let item2 = Item { v: sitems1[0].v + pitem.v, p: sitems1[0].p + pitem.p, q: 0 }; items[*k].push(item1); items[*k].push(item2); } items[*k].push(item); } let mut dp = vec![vec![0; (m / 10 + 1) as usize]; n + 1]; for j in 1..(n + 1) { if items[j - 1][0].q != 0 { // 附件不单独选择加入不加入背包,合并到主件中的主件+附件选择,跳过计算,只把上一层动态规划状态原样保存以便传递到下一层 for i in 1..((m / 10 + 1) as usize) { dp[j][i] = dp[j - 1][i]; } continue; } for i in 1..((m / 10 + 1) as usize) { // 初始不买j,用所有钱买j之前的商品的最优解 let mut maxi = dp[j - 1][i]; for l in &items[j - 1] { if i * 10 >= l.v { // 比较记录购买主件j的几种主件+附件组合l的最大值 maxi = maxi.max(dp[j - 1][i - (l.v / 10) as usize] + l.p); } } // 记录总金额i买或者不买主件j的最优结果 dp[j][i] = maxi; } } print!("{:?}", dp[n][m / 10 as usize]) }