一道送好多分的完全背包题。 题目描述 \(\text{Flappy Bird}\)是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道...
背包
完全背包问题 题解【有后效性的DP】【最短路】【背包】【同余】
后效性处理+背包合法性转化…又是玄学操作,不过感觉对DP的理解又深入了一些。 题目描述 有\(n\)种物品,物品的体积分别为\(V_1,V_2,\dots,V_n\),且每种物品的数量都可以看做是无限多的...
洛谷 P1272/POJ 1947 Rebuilding Roads 题解【树形DP】
它真的只是树形DP啊。。。 Description The cows have reconstructed Farmer John's farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake la...
洛谷 P1858 多人背包『第k优背包』 题解【DP】【背包】【归并】
DP套归并! 题目描述 求01背包前k优解的价值和,且背包必须装满。 输入输出格式 输入格式: 第一行三个数\(K,V,N\) 接下来每行两个数,表示体积和价值 输出格式: 前\(k\)优解的价...
洛谷 P1356 数列的整数性 题解【DP】【背包】【同余】
找规律啊…… 题目描述 对于任意一个整数数列,我们可以在每两个整数中间任意放一个符号'+'或'-',这样就可以构成一个表达式,也就可以计算出表达式的值。比如,现在有一个整数数列:17...
洛谷 P2732 商店购物 Shopping Offers 题解【DP】【背包】
可以说是暴力背包了吧。。。 题目背景 在商店中,每一种商品都有一个价格(用整数表示)。例如,一朵花的价格是 2 zorkmids (z),而一个花瓶的价格是 5z 。为了吸引更多的顾客,商...
洛谷 P2029 跳舞 题解【DP】【背包】
基础的(类似背包的)DP题。 题目描述 小明今天得到一个跳舞毯游戏程序Dance。游戏每次连续出N个移动的“箭头”,箭头依次标号为1到N,并且的相应的分数S[1..N]。如果你能“踏中”第i号...
洛谷 P2224 [HNOI2001]产品加工 题解【DP】【背包】【贪心】
像这种进程DP也是第一次见,不过只要把所有状态列出来,想做还是有好办法的。 题目描述 某加工厂有A、B两台机器,来加工的产品可以由其中任何一台机器完成,或者两台机器共同完成。由于...
NOIp模拟赛 数字【DP】【背包】【递推】【容斥原理】
DP思路有点难想的一个DP套递推题。为啥还要容斥原理 题目描述 一个数字被称为好数字当他满足下列条件: 1. 它有2*n个数位,n是正整数(允许有前导0)。 2. 构成它的每个数字都在给定的数字集合...
洛谷 P2515 [HAOI2010]软件安装 题解【tarjan】【树上DP】【背包】
写到快要崩溃-树上背包细节真的很多,有太多值得注意的地方。 题目描述 现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容...