WuliWuliiii

题解

/ 注册

全部文章 / 题解（共4篇）

最长树链【米勒罗宾+树的直径的简单树形DP】

很容易想到正确的解法，首先，我们可以知道（2 * 3 * 5 * 7 * 11 * 13 * ……）最多19个质数相乘就会达到1e9级别的。于是，我们可以考虑质数，我们可以知道一个数最多就是分成20个质数，所以我们直接进行对质数的检验会好一些。但是有些大质数应该怎么办呢？于是就有了米勒罗宾检验素数。...

数论 DP

2021-01-16

1 878

子序列【DP】

链接：https://ac.nowcoder.com/acm/problem/17065来源：牛客网有N个权值，a[1]……a[N]，现在要求一个子序列，满足对于所有的i<j，有。求解这样的子序列的个数。那么，我假设dp[i]表示以第i位为结尾的符合要求的子序列的个数，那么 ...

DP

2020-04-24

1 918

Rinne Loves Edges

树形DP首先，中文题，就不再阐述题意了。然后，具体怎么dp呢？首先不考虑树上，如果是一条序列上的话，肯定就是这条序列上的最小值了，现在其实实则变成了多条序列。我们动态规划的主要思想就是在于，是割下面的点的代价要小，还是割目前的边要更好些，所以用dp[u]记录，u结点为子树的根结点的时候，断开它到它的...

DP

2020-04-01

1 1293

芒砀山的神秘数字

DP + 组合数学首先，我们很容易的发现，如果数量是大于M的部分，是可以直接用组合数学来求解的，但是呢，前导0的情况，我们是要减去的。再看，剩下就是相等的部分了，我们可以写列写一个暴力DP来看。不难发现，每个点的值都是与之前的dp[1~i][j-1]相关联，但是，我们1～i可以通过01背...

DP 组合数学

2020-01-05

2 742