Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「HAOI2008」硬币购物 - 背包 DP + 容斥原理

    一共有 4 4 种硬币。面值分别为 c1,c2,c3,c4 c_1, c_2, c_3, c_4 。某人去商店买东西,去了 n n 次。每次带 di d_i ci c_i 硬币,买 si s_i 的价格的东西。请问每次有多少种付款方法?

    于  BZOJ, DP, HAOI, 容斥原理, 数学, 背包 DP 继续阅读

  2. 「SCOI2009」游戏 - 群论 + 背包 DP

    windy 学会了一种游戏。对于 1 1 N N N N 个数字,都有唯一且不同的 1 1 N N 的数字与之对应。最开始 windy 把数字按顺序 1,2,3,,N 1, 2, 3, \ldots, N 写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为 1,2,3,,N 1, 2, 3, \ldots, N

    如:1,2,3,4,5,6 1, 2, 3, 4, 5, 6 对应的关系为

    {122331455466 \begin{cases} 1 \rightarrow 2 \\ 2 \rightarrow 3 \\ 3 \rightarrow 1 \\ 4 \rightarrow 5 \\ 5 \rightarrow 4 \\ 6 \rightarrow 6 \end{cases}

    windy 的操作如下:

    这时,我们就有若干排 1 1 N N 的排列,上例中有 7 7 排。现在 windy 想知道,对于所有可能的对应关系,有多少种可能的排数。

    于  BZOJ, DP, SCOI, 数学, 群论, 背包 DP 继续阅读

  3. 「NOIP2014」飞扬的小鸟 - 背包 DP

    • 游戏界面是一个长为 n n ,高为 m m 的二维平面,其中有 k k 个管道(忽略管道的宽度)。
    • 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。
    • 小鸟每个单位时间沿横坐标方向右移的距离为 1 1 ,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度 X X ,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度 Y Y 。小鸟位于横坐标方向不同位置时,上升的高度 X X 和下降的高度 Y Y 可能互不相同。
    • 小鸟高度等于 0 0 或者小鸟碰到管道时,游戏失败。小鸟高度为 m m 时,无法再上升。

    现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。

    于  COGS, CodeVS, DP, NOIP, 背包 DP 继续阅读

  4. 「BZOJ 4247」挂饰 - 背包 DP

    JOI 君有 N N 个装在手机上的挂饰,编号为 1N 1 \to N 。 JOI君可以将其中的一些装在手机上。

    一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上,要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有 1 1 个。此外,每个挂件有一个安装时会获得的喜悦值,用一个整数(可以为负)来表示。

    JOI 君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰,而且一个都不挂也是可以的。

    于  BZOJ, DP, 背包 DP 继续阅读

  5. 「JSOI2008」魔兽地图 - 背包 DP

    游戏中,一些装备有价格,可以无限购买;另一些装备需要其它装备合成,这些装备有合成次数限制。每个装备都有膜法值,求 M M 个金币最多能得到多少膜法值的装备。

    于  BZOJ, DP, JSOI, 背包 DP 继续阅读

  6. 「HEOI2013」Eden 的新背包问题 - 背包 DP

    n n 个玩偶,每个玩偶有对应的价值、价钱,每个玩偶都可以被买有限次,在携带的价钱 m m 固定的情况下,如何选择买哪些玩偶以及每个玩偶买多少个,才能使得选择的玩偶总价钱不超过 m m ,且价值和最大。

    多次询问,每次询问都将给出新的总价钱,并且会去掉某个玩偶(即这个玩偶不能被选择),再问此时的多重背包的答案。

    于  BZOJ, DP, HEOI, 背包 DP 继续阅读

  7. 「SCOI2009」粉刷匠 - 背包 DP

    windy 有 N N 条木板需要被粉刷。每条木板被分为 M M 个格子。 每个格子要被刷成红色或蓝色。 windy 每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色。每个格子最多只能被粉刷一次。如果 windy 只能粉刷 T T 次,他最多能正确粉刷多少格子?

    一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷。

    于  BZOJ, DP, SCOI, 背包 DP 继续阅读

  8. 「BZOJ 1334」Elect - 背包 DP

    N N 个政党要组成一个联合内阁,每个党都有自己的席位数。现在希望你找出一种方案,你选中的党的席位数要大于总数的一半,并且联合内阁的席位数越多越好。对于一个联合内阁,如果某个政党退出后,其它党的席位仍大于总数的一半,则这个政党被称为是多余的,这是不允许的。

    于  BZOJ, DP, 背包 DP 继续阅读

  9. 「NOI2015」寿司晚宴 - 状压 DP

    给定 2 2 ~ n n n1 n - 1 个数,让两个人分别选出一些数,使得对于第一个人选择的任意一个数 a a 和第二个人选择的任意一个数 b b ,有 gcd(a,b)=1 \gcd(a, b) = 1 ,求方案数。

    于  BZOJ, DP, NOI, 状压 DP, 背包 DP 继续阅读

  10. 「UVa 11137」Ingenuous Cubrency - 递推 / 背包 DP

    给出一个正整数 N N N1000 N \leq 1000 ),求有多少种方案把 N N 表示成几个正整数的立方和的形式。

    于  DP, UVa, 数学, 背包 DP, 递推 继续阅读