Posts tagged with DP


老实说,这题我在现场赛大概写不出来。 感觉还是比较需要脑洞。 题意: 一排不同重量的蚂蚁按重量排成一排玩饥饿游戏,每只蚂蚁最开始选择一个方向,左或者右,大蚂蚁吃小蚂蚁,并且使自己增加小蚂蚁的重量,如果重量相同,左吃右。 问 n 只蚂蚁,第 k 只活到最后的方案数。 思路: 直接切入正解。 首先第k只蚂蚁必须选择左边,不然只能被吃。( $n \neq k $ ) 如果想要第…

/doge薛昊老是偷我题做,最近我也就拿他博客上的题来练练手。其中这道题真的什么思路都没有,这个区间DP的套路我还真没碰到过。 这是一个大区间推小区间的套路。 题意: 小明要在某层楼的各个老师那里交一大堆作业,但是小明来早了,老师还没上班,他站在这层楼的最左边,告诉你每个老师的上班时间,最后要在某个给定位置下楼,问最少时间。 思路: shit,完全是看博客,看代码敲的。 一个比较困难的点在于给定离开地点,算了,不装了,就算取消这个条件我也写不来…… 明确可以用dp求解,首先按照位置优先开门顺序次优的顺序排序,设三维数组 $dp[…

前几天的上分场的树形DP 我敢说思路和我当时想得已经一模一样了,还有半个多小时的时候,gou bi 带鱼说把题目给他看一下,然后立马得出,树形DP解不了,肯定是树分治! 当时我在一个子问题上走不出来,于是就信了,然后开始划水…… md 题意: 给你一棵树,要你给树上的每一个节点赋值,赋值存在范围,再给你一个特殊值,除开特殊值意外的数值赋值次数不限,但是特殊值的相邻节点的值不能是特殊值,也不能是比特殊值大的值。 问方案数。 思路: 首先值得注意的是,特殊值赋值次数不超过10,…

大概是第5次写矩阵快速幂…… 这道题在DP还是矩阵上都是属于简单范畴……,但没想到用DP就很烦…… 感觉矩阵加速还是挺有必要学一下的…… 顺带学了一下什么叫分数取模用逆元 题意: 让你抛 k 次 硬币,求上面朝上的次数为偶数的概率。 单次正面朝上的概率为 ( \dfrac {q} {p} ) 思路: 令 dp [ n ] [ 0 ] 表示抛了 n 次后,朝上次数为偶数的概率,dp[…

一道二分图性质的应用 + 树形DP ? 看博客里都说是树形DP,但我觉得应该是树上前缀和更加合适一些 题意: 给你一个图,让你删除一条边,使得剩下的图是二分图。 输出可删边数并顺序输出边的序号。 思路: 首先你必须知道判定二分图的充要条件 —— 不存在奇环。 如果只是让你判定二分图的话,倒是随便搜一遍就可以解决的问题。 但是这里必须让你删掉一条边…… 写不来……感觉不好写,最后无奈去看题解了…… 先整理一下判断思路: 如果不存在奇环,那么原图本来就是一张二分图,每一条边都满足条件 覆盖了所有的奇环,并且不能覆盖偶环的所有边 为什么同时不能覆盖偶环,…