和题解的DP方法不一样，,代表前i个宝石考虑完了之后剩下j块钱的最大价值 考虑对于普通宝石 = 然后考虑魔法宝石对于每种魔法宝石，可以考虑与前面的魔法宝石发生碰撞位置L和位置R的魔法宝石发生碰撞情况只有这个区间内的魔法宝石数量是偶数，且L和R都是魔法宝石，那么就可以从内到外的不断碰撞，直到最后L和R位置的宝石发生碰撞，区间能发生碰撞的话，能够获得的权值也是固定的，就是区间内普通宝石的权值，区间能发生碰撞的话，所消耗的钱也是固定的，就是区间内魔法宝石的权值。 区间内普通宝石的权值前缀和，区间内魔法宝石的权值前缀和 在位置R是魔法宝石时的转移为,满足上述要求, 这就是转移式子，后面是分析偶数个魔...

rt

https://blog.csdn.net/qq_43804974/article/details/105345340昨天的牛客鸽了，我不会数学 首先第一步要理解题意就是要把树分成多个联通块，每个联通块的颜色都要不一样，求方案数。为什么每个联通块的颜色都不一样，因为如果有同样的颜色在不同的联通块上的话就无法满足题意，这两个点之间的路径的所有点就不会是都是同一种色。 用f[i][j]代表的是以i为根的子树分成j个联通块的的方案数。由于我没想到大佬说的分成j个联通块就是删掉j-1条边，所以就硬算去合并每个子树的答案。暴力合并就复杂度变成n^3; 得到每种联通块的方案数后就是组合数学算一下就好了，...

https://blog.csdn.net/qq_43804974/article/details/105269874首先这个数据范围，看着就是O(N)或者O（Nlogn）的东西，考虑树dp。先贪心的考虑。一个点怎么找到另一个点？肯定是他能接触到的最短的那个点，如果与他最短的那个点被用过了呢？找其他第二近的点，以此类推。对于一个点，是只有当找不到人了才会继续走上去找其他人匹配，不然不管多大的权值都是会跟那个人走的。因为对于一条权值很大的边，边连着的两个点如果深度深的点在往下匹配不到人，就必须走上匹配，最少需要经过这条边一次，那么对于一个必须经过这个边的点他肯定是与另一个无法匹配的点去结合，不管...

https://blog.csdn.net/qq_43804974/article/details/105241744 问题就是询问某一个串是不是初始串的子序列。那么序列都是小写字母，就对存入每一个字母在初始串的位置。然后对目标串的字母一个个查询，如果存在一个最接近并且比上一个字母远的位置，则这个当前字母是存在序列中的，不断的遍历完整个目标串就可以了。开个vector，upper_bound真香 char node[max_],temp[max_]; vector<int> ind[30]; signed main() { // scanf_s("%s",...

https://blog.csdn.net/qq_43804974/article/details/105222630 首先理解题意后可以转化为以S为根的树，用最少的权值去删除边，使得所有的叶子与S不相连。如果可以得出上面的题意那这题就是个树dp简单题了。那么设f[i] 为以i为根的子树，他的所有叶子都达不到i节点的最少权值花费。显然方程就是f[i] = sum( min ( f [to], i与to相连的权) )这个方程就是对于i的每一个儿子，你有两种选择，第一种是砍掉i与to相连的边，这样所有叶子都不会到达i，一种的利用f[to]算好的答案，取一个最小值答案就是f[S] int n, m...

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];然后只要倍增得到dp[i][0]就可以了。对每个询问新建立节点，这样找答案就很方便，而且也不会出现错误答案，因为新建立的节点必定是叶子节点，所以不会对其他答案造成影响。还有就是倍增的时候可以利用lg[深度]去稍稍优化一下，下面代码跑了181ms #include<iostream> #inc...

https://blog.csdn.net/qq_43804974/article/details/105176524这道题由于空间限制的很死，所以原本用线段树之类O(nlogn)的算法都会MLE，唯一的做法就是O（N）的单调队列。 对于每一个滑动窗口的元素，都是从上一个窗口的基础上，增加一个新的元素，减掉一个最后的元素。就利用单调双端队列去处理问题，对于一个新的窗口就push进去，然后不断pop直到出现第一个合法的元素，那个元素就是我们要的这个窗口内的最值的答案，不合法的元素是什么意思呢，就是你这个元素所在的位置太前了， 这个窗口的区间包含不到他，所以只能删掉。 #include<i...

https://blog.csdn.net/qq_43804974/article/details/105115539 虽然说是动态规划实则就是在暴力找答案。我们答案要求的是两个区间，所以我们只要选取一个区间，然后枚举这个区间往前的所有区间能提供的最大答案就好了。我们需要什么呢value[i] , 区间的最后位置是i，这个区间的权值总和.这个value可以用前缀和轻松算。下一个就是fmax[i],代表的是[1,i]这些位置能构成的最大区间权值然后答案明显就是 ans = max(ans, value[i] + fmax_[i - k]); 当我们写出value数组后就可以直接写出fmax数组了...

https://blog.csdn.net/qq_43804974/article/details/105103097首先这种题肯定是动态规划！！！！！不要往其他地方想。要怎么做呢先从单个串要怎么判断区间最长回文来说。 单个串如果要判断任意一个区间[L,R]是不是回文可以去写区间dp，对于一个串长度大于2的回文串，如果要在此基础上在延长串的长度必然是在头尾加两个，所以对于一个串的就可以写出方程 f[L][R] |= F[L+1][R-1],(当a[L]==a[R]时)； 现在到了两个串，其实思路差不多，两个串要拼出一个回文串也必然要在原先满足的基础上在加两个字母。那么我们这么设计状态f[i][...

考虑我们可以怎么获得答案，如果某一个人选了他，那么答案人数的集合就必定小于等于s[i], 对于答案需要的人的集合的人数为num,那么集合里面所有的s[i]的最小值必然是小于等于num。 明确了上述最关键的点后就是可以知道，我们如果答案的人数是2人，则s[i]>=2的全部人数取前2个就是答案，s[i] < 2的被我们排除了。那么解题步骤就是设目标人数是num人，取s[i] >= num的人中权值最大的前num个。 我们就可以从选一个人开始枚举，然后现在要选num人，就可以把s[i]为num-1的人给删掉，因为选取的人数是不断增加的，所以这个被删掉的点在后面也是不可能满足条件的。...

题意是叫你找最长的回文串，然后这个回文串可以由原本的串的前驱+后继拼起来。 由于前驱和后继是必须选的对不对（可能有一个为空）。 那么我们第一步就是吧原本的串倒置，把正的和反的去找出最长的相同的，这样就满足了前驱+后继的限制。下一步是什么？ 假设原本的长度是[1,len]，我们上面找到的最长相同的长度是3，那么就是接下来剩下的串就是[1 + 3 - 1 , len - 3],剩下的这一段我们只需要找到两个端点为开头的最长回文串就好了。如图所示。 为什么是两个端点？如果选取了左端点则说明我们与前驱的串接上去了。如果选择了右端点，这说明我们与后继的串接上去了。这样就满足了题意。要求这个的长度我...

题目大意：给你个有向无环图，询问从1到n的路径里面，时间小于T的，但是路过点数是最多的路径。求点数 n，m只有5000，所以大胆一点，n^2的算法就冲上去。题目要什么我们的dp就设计什么。 设f[i][j]有两个权值v1,fa; 意义是从1走到i走过了j个点的最小权值。走到i点的前一个点是fa。 那么只要做一次拓扑排序，拓扑排序后就可以做一个线性的dp。不做拓扑会可能发现某个点还没被更新但是你就在利用这个点走下一个了。 这个dp怎么转移呢 就是从f[i][j]转移到f[to][j+1]就可以了，也就是枚举i的所有出边，计算权值就够了。 最后的答案就是在f[n][k]找到最大的k，逆序输出就好...

题目大意就是有n个门，m个机关，机关对应的是k个门，点击机关m则k个门的状态全部反转。询问是否存在一种方式让所有门都变为1；每个门都是只有两个机关可影响到他。 分析一下问题可以知道，对于门初始为1，则这个门对应的两个机关只能一起选，或者都不选，也就是这两个机关是被绑定着的。 对于门初始为0，则这个们对应的两个机关只能选一个，选了A就不能选B，选B,就不能选A； 考虑机关只有选与不选对不对。我们这么去假设，设置种类并查集pre[i]和pre[i + m],pre[i]指的是i的同类，pre[i + m]是指i的敌对面。对于上面的每个机关，我们都可以对应的去连线。 （1）对于门i为1，t1,t2...