boxxxx

分类

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

/ 注册

全部文章（共55篇）

题解 | #Kevin的宝石#

和题解的DP方法不一样，,代表前i个宝石考虑完了之后剩下j块钱的最大价值考虑对于普通宝石 = 然后考虑魔法宝石对于每种魔法宝石，可以考虑与前面的魔法宝石发生碰撞位置L和位置R的魔法宝石发生碰撞情况只有这个区间内的魔法宝石数量是偶数，且L和R都是魔法宝石，那么就可以从内到外的不断碰撞，直到最后L和...

C++ 动态规划数组

2023-12-02

1 380

牛客每日一题 4.7 树树dp+组合数学

https://blog.csdn.net/qq_43804974/article/details/105345340昨天的牛客鸽了，我不会数学首先第一步要理解题意就是要把树分成多个联通块，每个联通块的颜色都要不一样，求方案数。为什么每个联通块的颜色都不一样，因为如果有同样的颜色在不同的联通块上...

动态规划

2020-04-06

0 676

牛客每日一题4.3 Shortest Path 树dp

https://blog.csdn.net/qq_43804974/article/details/105269874首先这个数据范围，看着就是O(N)或者O（Nlogn）的东西，考虑树dp。先贪心的考虑。一个点怎么找到另一个点？肯定是他能接触到的最短的那个点，如果与他最短的那个点被用过了呢？找其他...

2020-04-02

0 611

牛客每日一题4.2 月月查华华的手机二分查找

https://blog.csdn.net/qq_43804974/article/details/105241744 问题就是询问某一个串是不是初始串的子序列。那么序列都是小写字母，就对存入每一个字母在初始串的位置。然后对目标串的字母一个个查询，如果存在一个最接近并且比上一个字母远的位置，则这个当...

2020-04-01

0 689

牛客每日一题4.1 Rinne Loves Edges 树dp

https://blog.csdn.net/qq_43804974/article/details/105222630 首先理解题意后可以转化为以S为根的树，用最少的权值去删除边，使得所有的叶子与S不相连。如果可以得出上面的题意那这题就是个树dp简单题了。那么设f[i] 为以i为根的子树，他的所有叶...

dp

2020-03-31

0 591

牛客每日一题3.31 城市网络树上倍增

https://blog.csdn.net/qq_43804974/article/details/105196280 数据修复后，之前的就T掉了~还是树上倍增，dp[i][j]就是节点i开始拿了2^j个物品后所在的位置，递推就是dp[i][j] = dp[dp[i][j-1]][j - 1];然后...

2020-03-30

0 672

牛客每日一题3.30 滑动窗口单调队列

https://blog.csdn.net/qq_43804974/article/details/105176524这道题由于空间限制的很死，所以原本用线段树之类O(nlogn)的算法都会MLE，唯一的做法就是O（N）的单调队列。对于每一个滑动窗口的元素，都是从上一个窗口的基础上，增加一个新的...

2020-03-29

0 714

牛客竞赛每日一题3.27 数学考试动态规划

https://blog.csdn.net/qq_43804974/article/details/105115539 虽然说是动态规划实则就是在暴力找答案。我们答案要求的是两个区间，所以我们只要选取一个区间，然后枚举这个区间往前的所有区间能提供的最大答案就好了。我们需要什么呢value[i] , ...

2020-03-26

0 841

牛客每日一题3.26 合并回文子串动态规划

https://blog.csdn.net/qq_43804974/article/details/105103097首先这种题肯定是动态规划！！！！！不要往其他地方想。要怎么做呢先从单个串要怎么判断区间最长回文来说。单个串如果要判断任意一个区间[L,R]是不是回文可以去写区间dp，对于一个串长度...

动态规划 dp

2020-03-25

0 666

牛客每日一题3.25 tokitsukaze and Soldier 权值线段树

考虑我们可以怎么获得答案，如果某一个人选了他，那么答案人数的集合就必定小于等于s[i], 对于答案需要的人的集合的人数为num,那么集合里面所有的s[i]的最小值必然是小于等于num。明确了上述最关键的点后就是可以知道，我们如果答案的人数是2人，则s[i]>=2的全部人数取前2个就是答案，s...

2020-03-24

0 779