AT2390 Games on DAG 题意 \(n\) 个点 \(m\) 条边的 DAG，每条边 \((u,v)\) 有 \(u<v\)。\(1,2\) 号点各一个石头，Alice 和 Bob 轮流每次沿边移动一个石头，不能动者输。求所有连边子集中先手胜的情况。两个石头可以重合。\(n\leq 15\)。 思路 发现对于两个石头的 SG 函数是独立的，输者两个石头 SG 函...

AT2304 Cleaning 题意 一个树上每个节点有一些石子，每次只能选取两个叶子节点并将路径间的所有点上的石子数量减1，问是否能将所有石子取完。 思路 设 \(f_x\) 表示从 \(x\) 节点向上的路径条数，\(s_x\) 为子节点的 \(f\) 值的和，则有： \[ a_x=\frac{s_x-f_x}{2}+f_x\\ f_x=2a_x-s_x \] 我们只需要保...

CF175E Power Defence 题意 一个塔防游戏：给定一个无限长的数轴，一个无限血的敌人要从正无穷走到负无穷。你的任务是放置三种塔，包含两种攻击塔和一种寒冰塔，使得敌人受到的伤害最大。 其中，每种塔的攻击半径可能不同，每种攻击塔的攻击力也可能不同。而寒冰塔没有攻击力，它的作用是使范围内敌人的速度减速，即一段区间若有\(k\)个寒冰塔覆盖，敌人速度变为\(\frac{1}{k...

CF404D-DP 正经的东西 题意 给定一个字符串，只包含'0','1','2','*','?'五种字符，其中'?'可被替换为其他任何一种，求使序列符合扫雷地图定义的方案数。 一个数字字符大小表示与之临近的位置总共有多少个雷。 思路 DP。 和其他题解不太相同，我们每个点只记录三种状态：0,1,2，分别表示若此点的下一位不为雷、为雷和此点位就是雷的此位及以前的方案数。 ...

CF459E-DP 核心代码15行 思路 观察数据范围，我们建m层分层图跑最短路想到DP。 DP最大的特点就是无后效性。那么我们这一题哪个条件无后效性呢？ 发现DP值一定从边权小于当前点的位置转移而来。 这不就无后效性了？我们按边权将所有边排序即可。 然后，枚举边，将DP值记录到点上，每次用起始点的dp值加1更新到达点的dp值。最后输出dp值最大的即可。 然后，您会发现第一个...

CF833B-线段树优化DP 题意 将一个长为\(n\)的序列分成\(k\)段，每段贡献为其中不同数字的个数，求最大贡献和。\(n\leq 35000,k\leq 50\)。 思路 此处感谢@gxy001 聚铑的精彩讲解 先考虑暴力DP，可以想到一个时空复杂度\(O(n^2k)\)的方法，即记录前i个数字分成了j段。我们现在来思考几个问题来优化这个操作： 对于一个数字，它对那...

CF494D Birthday 题意 一个1为根的带边权有根树，每次询问给定两个点 \(u,v\) 求 \(\sum_{x\in S(v)} d(u,x)^2-\sum_{x\not\in S(v)}d(u,x)^2\) 其中 \(d(u,v)\) 表示 \(u,v\) 简单路径长度， \(S(u)\) 表示 \(u\) 的子树内点的集合。 思路 考虑 \(u\) 在 \(v\)...

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 了。 对于输出前序遍历（根，左树，右树）我们再...

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

洛谷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]无...