博客
归档
友链
关于
博客
归档
友链
关于
容斥+背包学习笔记
有时候,我们在做背包问题时会遇到如下情况,给你一大堆询问,要你求出满足某种限制,填满背包的方法数。 先来一道例题: 例题1: P1450 [HAOI2008]硬币购物 乍眼一看似乎是一个裸的完全背包,但是注意到询问组数较多,每次跑一遍完全背包绝对会炸掉,考虑预处理出不带限制的方法数,然后用容斥除去不满足限制的方法。 预处理,用题目的四种硬币凑出xxx元的钱共有f(x)f(x)f(x)种方法...
2019-08-25
阅读全文
[POJ2229] [USACO 2005 January Silver] Sum sets
一个裸的完全背包,考虑将2k2^k2k当做物品,做完全背包即可。 12345678910111213141516171819202122232425262728293031323334353637#include <iostream>#include <cstdio>#define MAXN 1000005#define MAXM 24#define MOD 1000...
2019-07-24
阅读全文