第一次遇到概率/期望DP,收获挺多。 题目描述 你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物,每次你都可以选择吃或者不吃(必须...
DP
洛谷 P2915 [USACO08NOV]奶牛混合起来Mixed Up Cows 题解【状态压缩】【DP】
很久没做过状压DP了,这道状压DP有很多技巧 题目描述 Each of Farmer John's N (4 <= N <= 16) cows has a unique serial number S_i (1 <= S_i <= 25,000). The cows a...
洛谷 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两台机器,来加工的产品可以由其中任何一台机器完成,或者两台机器共同完成。由于...
洛谷 P3629 [APIO2010]巡逻 题解【树的直径】【树形DP】【贪心】
这个题真的只考树的直径啊。。。 题目描述 在一个地区中有n个村庄,编号为1, 2, ..., n。有n–1条道路连接着这些村 庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到...
洛谷 P2607 bzoj1040 [ZJOI2008]骑士 题解【基环树】【树形DP】
互相讨厌以后是不是成树形DP标志了。。。:( 题目描述 Z国的骑士团是一个很有势力的组织,帮会中汇聚了来自各地的精英。他们劫富济贫,惩恶扬善,受到社会各界的赞扬。 最近发生了一件可...
NOIp模拟赛 数字【DP】【背包】【递推】【容斥原理】
DP思路有点难想的一个DP套递推题。为啥还要容斥原理 题目描述 一个数字被称为好数字当他满足下列条件: 1. 它有2*n个数位,n是正整数(允许有前导0)。 2. 构成它的每个数字都在给定的数字集合...
洛谷 P1725 琪露诺 题解【DP】【单调队列】【线段树】
一道O(N)的题又在考场上打了暴力线段树。。。 题目描述 在幻想乡,琪露诺是以笨蛋闻名的冰之妖精。 某一天,琪露诺又在玩速冻青蛙,就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要...
计蒜客 16447 蒜头君的坐骑 题解【DP】【搜索】
原来DP还分刷表法和填表法啊…… 题目描述 蒜头君有一只坐骑,人马。 一天,蒜头君骑着他的坐骑走上了一片 n×m 的大荒野,一开始时,蒜头君在 (1,1) 点,他要前往(n,m) ...