题解 | #购物单#

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])

}