boxxxx

分类

学习(10) 并查集(1) 数位dp(1) 概率dp(1) 算法(38) 线性dp(1) 题解(3)

/ 注册

全部文章（共55篇）

Codeforces Global Round 7 cf 1326D 马拉车

题意是叫你找最长的回文串，然后这个回文串可以由原本的串的前驱+后继拼起来。由于前驱和后继是必须选的对不对（可能有一个为空）。那么我们第一步就是吧原本的串倒置，把正的和反的去找出最长的相同的，这样就满足了前驱+后继的限制。下一步是什么？假设原本的长度是[1,len]，我们上面找到的最长相同的...

2020-03-20

0 572

cf721 C DP

题目大意：给你个有向无环图，询问从1到n的路径里面，时间小于T的，但是路过点数是最多的路径。求点数 n，m只有5000，所以大胆一点，n^2的算法就冲上去。题目要什么我们的dp就设计什么。设f[i][j]有两个权值v1,fa; 意义是从1走到i走过了j个点的最小权值。走到i点的前一个点是fa。 ...

2020-03-18

0 621

cf776 D 并查集

题目大意就是有n个门，m个机关，机关对应的是k个门，点击机关m则k个门的状态全部反转。询问是否存在一种方式让所有门都变为1；每个门都是只有两个机关可影响到他。分析一下问题可以知道，对于门初始为1，则这个门对应的两个机关只能一起选，或者都不选，也就是这两个机关是被绑定着的。对于门初始为0，则这个...

2020-03-18

0 529

牛客练习赛59 E 石子搬运 dp+三分法

有n堆石子，第i堆石子的石子数量是ai{a_{i}}ai，作为牛客网的一头领头牛，牛牛决定把这些石子搬回牛客。如果牛牛一次搬运的石子数量是k{k}k，那么这堆石子将对牛牛产生k2{k^{2}}k2的负担值。牛牛最多只能搬运m{m}m次，每次搬运可以从一堆石子中选出一些石子搬回牛客，每次搬运不能同时...

2020-03-14

0 635

洛谷p1831 数位dp

补充点在其他题解里面没有的其他东西。首先是之所以可以数位dp并且不会算错的原因是，对于每一个数字，如果这个数字是杠杆数，那么他的支点有且只有一个，如果一个数字有多个支点，那么数位dp去枚举支点就会算重复，算多。另外全部人都是在说数位dp然后枚举支点，对R和L-1分别做一次dp，但是可以有个小...

2020-02-27

0 484

洛谷p2059 概率dp

首先仔细读题目按顺时针从庄家位置数第X个人将被处决即退出游戏， x为1的时候被处决的就是庄家，千万不要理解错位庄家的位置+x就是被处决人的位置，我一开始就是这么理解然后调完发现怎么加起来答案是1但是和样例长的不一样我们思考下怎么做，对于如此小的数据范围，肯定是可以枚举每一次游戏某一个人获得胜利...

2020-02-25

0 795

洛谷p2018 树DP

首先，本做法和其他的O(N^2logn)做法是完全不一样的，那种做法比较好理解，我说一下我的做法，感jio是O(Nlogn)，不太会算首先思考如何获得每一点要如何知道由当前点出发的答案是什么？对于绝大部分点，都有父亲节点和儿子节点，那么对于每一个点都是这么抉择走的。这里先不看now点，看节点1...

2020-02-16

0 439

洛谷p1773 dp

其实，这个dp还是蛮简单的，dp做多了后就会觉得方程不难出了，其实我的思路和大家都差不多，但是大部分都用了O(N^2)去预处理出这个区间内的值取模后是多少，其实这是完全没有必要的。听我来给你吹 f[i][j] = v：前i个字符各种操作后的数字为j，使用的最少的乘法个数为v，最后一个字符必须要落...

2020-02-14

0 504

洛谷2285 dp

很水的dp，用于在你蓝题dp做疯了的时候来提高下信心。首先那个距离就是曼哈顿距离，所以小于等于1的格子就是当前格子的上下左右，还包含自身。其实唯一的问题就是如何计算贡献的时候不要算重复了，那么分情况考虑就可以不算重复，f[i][j][0]代表到达ij点的走法是从上面走下来，f[i][j][1]代...

2020-02-11

0 427

洛谷p2964 其中一种常见的博弈论的dp方法

题目链接在之前，我写dp看见题目说两个人都足够聪明，然后他们进行一些操作，求某些人的最大利益，我完全不知道怎么去设计dp的方法，然后我接触了一道题，看了题解洛谷p2734 这道题的dp方法和现在这道题其实在设计思路上面是一样。我不知道现在是谁在取数字，但是我就是要为现在这个取数字的人谋取最大...

2020-01-30

0 594