wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共7篇）

【每日一题】失衡天平

problem 将个物品分成两堆，使得两堆重量之差不超过m。问两堆重量之和最多是多少。 solution 用表示前i个物品，左边一堆的重量减去右边一堆的重量为j，最大的重量之和。对于一个物品有放在左边，放在右边，不放三种决策。对于重量为x的物品如果放在左边，就有如果放在右边，就有如果不放，就有$...

背包

2020-06-10

1 915

【每日一题】货币系统

solution 想起当年noip赛场上没做出来这道降智题就来气。。。这个题目其实讲的也就是去掉最多的元素，使得剩下的元素可以组成原来可以组成全部数字。仔细想一下，其实就是将原数组排序之后，如果比较大的那个可以被比较小的表示出来，那么这个元素我们就可以删去了。所以我们用表示前i个元素是不是可以组...

背包动态规划

2020-05-26

1 559

【每日一题】简单瞎搞题

solution 用表示前k个区间能(1)不能(0)组成这个数字。然后枚举一下第个区间所选的数字x，就有转移最后数一下有多少数字可以被组成就行了。但是这样复杂度爆炸，发现f的值只有和所以可以用进行优化，复杂度 code /* * @Author: wxyww * @Date: 2020-05...

背包 bitset

2020-05-19

2 0

hdu1085 Holding Bin-Laden Captive!

solution 有两种解法。解法一：分组背包，相当于有3种物品，分别有个，重量分别是。问不能组成的最小的重量。用表示这个重量能不能组成。然后将分组背包拆成01背包做。枚举一下重量，看是否能组成。解法二：生成函数。用表示选择1能组成的方案。用表示选择2能组成的方案。用表示选择5能组成的方案...

生成函数背包

2020-04-16

1 626

hdu1028 Ignatius and the Princess III

solution 此题有两种解法。第一种解法就是裸的完全背包。就相当于有n种物品，第i种物品的重量是i。每种物品有无限多个，问恰好填满一个容量为n的背包的方案数。第二种解法是生成函数。用生成函数表示拆分出的的数量。用表示拆分出的的数量。剩下的同理。最终的系数就是答案。 code 解法1 /*...

生成函数背包

2020-04-16

1 718

hihocoder1364 奖券兑换

题目链接思路乍一看这是一个01背包的裸题。但是数据范围\(10^5\)是无法承受的。但是发现\(p_i\)和\(w_i\)只有10，也就是说最多只有100种物品。所以可以对他们进行分组。然后用二进制优化多重背包来做。二进制优化多重背包多重背包是指限定物品数量的一种背包问题。多重背...

动态规划dp 背包

2019-01-24

0 443

hihocoder1364 奖券兑换

题目链接思路乍一看这是一个01背包的裸题。但是数据范围\(10^5\)是无法承受的。但是发现\(p_i\)和\(w_i\)只有10，也就是说最多只有100种物品。所以可以对他们进行分组。然后用二进制优化多重背包来做。二进制优化多重背包多重背包是指限定物品数量的一种背包问题。多重背...

动态规划dp 背包

2019-01-24

0 493