Accumulation Degree

Accumulation Degree
这题简单来说就是任意根到子树的最大流量,这题假如我们枚举n个点的话,我们可以用O(n^2)时间做出这一题,但是呢,n很大,所以呢我们要至少减去一个log的复杂度,又因为我们只枚举一个任意点进行一次DP就可以获得大多数其他点DP得到的结果,所以我们先DP一次,然后再利用dfs计算DP取得的数据据算出其他点的数据。 ......  查看更多

没有上司的晚会

没有上司的晚会
这题的话我们可以把直接上司和员工连一条边,这里f[x][0]表示我不让x来的最大快乐值,f[x][1]表示让x来的最大快乐值,那么我们每次dfs下去回溯时,就分f[x][1]+=f[x][0]f[x][0]+=max(f[y][0],f[y][1]),分情况讨论一下,最后输出max(f[1][0],f[1][1])即可

 ......  查看更多

选课

选课
选课这一题我们很容易发现没有根节点,因为可能不止一个不用前置课程的节点,然后我们因为多个课程可能有一个相同的前置课程,所以我们其一可以通过森林转二叉树进行就是左孩子右兄弟,或者采用背包型树形DP,把每一次树形DP的结果都做一个背包,这样子用f[x][t]代表以x为跟的子树选t个节点的最大值,然后再回溯时背包一下,就可以用不同的t取得不同f[x][t]结果,然后就可以正常动归了! ......  查看更多

「算进」[动归]树形DP

动态规划问题是大家都很熟悉的问题了,那么好了,树形DP顾命思意就是在一棵树上DP,解决一些问题,那么我们可以采用Dfs+边目录的方式来处理这些问题。通常来说从x节点递归下去,然后回溯上来,递归的数据x转移。

没有上司的舞会

这题的话我们可以把直接上司和员工连一条边,这里f[x][0]表示我不让x来的最大快乐值,f[x][1]表示让x来的最大快乐值,那么我们每次dfs下去回溯时,就分f[x][1]+=f[x][0]f[x][0]+=max(f[y][0],f[y][1]),分情况讨论一下,最后输出max(f[1][0],f[1][1])即可
AcceptCode ......  查看更多

[AHOI2005]病毒检测

[AHOI2005]病毒检测
这个可以给出O(n^3)复杂度的代码,肯定就是O(n^3)啦,没有质疑的空间了。那么有什么代码开一跑怎么快呢,DP,DFS,贪心。
这里的话我们就用DP解一下这题
F[i][j]代表母串匹配i个,字串匹配到j个时可不可以匹配到。
然后更新一下,注意*要特判一下,因为他可以匹配很多个字符。 ......  查看更多

[ZJOI2010]count 数字计数

[ZJOI2010]count 数字计数
%%%静静 and 楠楠
这题就是数位DP的裸题,然而我还是要%题解,自己写的代码调不出来
f[i][j][k]表示若前i个位置有kj的此时的全局方案数
然后就是记忆化搜索

挂饰

bzoj-挂饰
先给DP方程
f[i][j]=max(f[i-1][j],f[i-1][max(j-a[i].w,0)+1]+a[i].x)

f[i][j]表示前i个挂饰选完(可以有不选)之后还剩下j个挂钩的最大值 j最多贡献为n