WuliWuliiii
WuliWuliiii
全部文章
分类
题解(12)
归档
标签
去牛客网
登录
/
注册
WuliWuliiii的博客
全部文章
(共4篇)
最长树链【米勒罗宾+树的直径的简单树形DP】
很容易想到正确的解法,首先,我们可以知道(2 * 3 * 5 * 7 * 11 * 13 * ……)最多19个质数相乘就会达到1e9级别的。于是,我们可以考虑质数,我们可以知道一个数最多就是分成20个质数,所以我们直接进行对质数的检验会好一些。但是有些大质数应该怎么办呢?于是就有了米勒罗宾检验素数。...
数论
DP
2021-01-16
1
877
子序列【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
1292
芒砀山的神秘数字
DP + 组合数学 首先,我们很容易的发现,如果数量是大于M的部分,是可以直接用组合数学来求解的,但是呢,前导0的情况,我们是要减去的。 再看,剩下就是相等的部分了,我们可以写列写一个 暴力DP来看。不难发现,每个点的值都是与之前的dp[1~i][j-1]相关联,但是,我们1~i可以通过01背...
DP
组合数学
2020-01-05
2
742