P1040 加分二叉树 \(n\) 很小，可以树形 dp 或者区间 dp 。 设 f[i][j] 为从 \(i\) 到 \(j\) 的最大加分值，则有 f[i][j]=max(f[i][k-1]*f[k+1][j]+f[k][k])。 有一个小技巧，将 f[i][i-1] 全部设置为 1，这样的话搜索到叶子就也可以按照通式 dp 了。 对于输出前序遍历（根，左树，右树）我们再...

P1414 又是毕业季II 数论题，主要在于推演。 洛谷的《又是毕业季I》更好玩 发现对于所有的同学的能力值，只要我们选出每个数的所有因子并记录所有同学所有因子出现的次数，就可以得到一个 \(c\) 数组为所有因子出现的次数。 因为让输出 \(1\sim n\) 所有的值，而且因子数 c[k-1]>=c[k]，我们就一定可以从因子数最高的 \(c\) 向下遍历到 c[i...

P1447能量采集 定义:(i,j)表示处于(i,j)的植物的贡献 我们发现，点(i,j)与(0,0)的连线所过整点的数目为\(\gcd(i,j)\) 发现要是想记录每个点的答案并不好算。那么怎么好算呢？ 我们来找一找同一直线上的所有点答案的和的关系。先不考虑答案只考虑个数。发现，寻找一个点及其倍数的个数的和更加好算。而且，因为有n和m的限制，那么向下取整的答案一定就是其本身...

P1880 [NOI1995] 石子合并 一道区间dp题目。 用 d[i][j] 表示从 i 到 j 的最大/最小得分，那么依次枚举长度 len，坐标 i 和 j，三层循环就可以 dp递推求得最值了。 （如果没有环的话） 不要着急，我们将序列复制一遍接到后面做一遍即可。 12345678910111213141516171819202122232425262728293031...

莫队算法的待修版本，增加一个时间的维度进行分块。 P1903 [国家集训队] 数颜色 / 维护队列 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757...

洛谷P2014选课 一道树形DP题。 f[i][j] 表示i个点选j门课程的最大学分。 递推方程： 1234for(int a=n;a>0;a--)//总共选择多少 for(int b=0;b<a;b++)//分别选择多少(b,a-b) f[x][a]=max(f[x][a],f[x][a-b]+f[u][b]);//都不遍历0的原因是f[i][0]无...

P2476-记忆化搜索 DP? 我们看看，这个状态似乎有亿点点多。我们看看数据范围，数量不超过5，颜色数不超过15. 15维DP显然不靠谱。 那么我们就思考一下……状态个数？发现记忆化搜索可ac： 1234567891011121314151617181920212223242526272829303132#include<iostream>#include<cs...

P2375 [NOI2014]动物园 我竟然会做NOI的题目辣(≧▽≦)/（看的题解 总而言之，这是一道简单的KMP问题。题面简直是给没学过KMP的人看的（比如我）。 我们发现，这个所谓的 num 数组和 nxt 有异曲同工之妙。但是我们对于不能重合这一块有一点问号。那我们先不管重不重合，先给他记录成重合的。 于是在标记 nxt 时同时也可以把 num 标记。原理是，nxt ...

P2490 [SDOI2011]黑白棋 题意 一个 \(1*n\) 的棋盘上，A 可以移动白色棋子，B 可以移动黑色的棋子，其中白色不能往左，黑色不能往右。他们每次操作可以移动 1 到 \(d\) 个棋子。 每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。 思路 显然可以将题意转化为一种 K-Nim 游戏，即在 \(\frac...

P2491 消防/P1099 树网的核 双倍经验，双倍快乐。 题意 在一个树上选择一段总长度不超过\(s\)的链使所有点到该链距离的最大值最小。 输出这个最小的值。 做法 Define:以下\(s\)指链或链长。 证明一下\(s\)一定处于直径上。假设它不在直径上，一定存在直径的其中一个端点到\(s\)的距离大于现在所处支链的最大距离。所以\(s\)不在直径上一定不优。 ...