收录一些比较冷门的DP优化方法。1.树上依赖性背包树上依赖性背包形如在树上选出若干个物品做背包问题，满足这些物品连通。由于01背包，多重背包和完全背包均可以在\(\mathcal{O}(V)\)的时间内加入一个物品，\(\mathcal{O}(V^2)\)的时间内合并两个背包，所以不妨设背包类型为多重背包。先考虑一个弱化版问题。给定一棵有根树，若一个节点被选，则它的父亲必须被选。显然存在一个\(\mathcal{O}(nV^2)\)的树形DP做法，它能求出以每个节点为根时其子树的答案。接下来引出科技：树上依赖性背包。我们发现对每个节点都求答案似乎有些累赘，因为我们只关心以\(1\)为根时的答案
收录一些比较冷门的DP优化方法。1.树上依赖性背包树上依赖性背包形如在树上选出若干个物品做背包问题，满足这些物品连通。由于01背包，多重背包和完全背包均可以在\(\mathcal{O}(V)\)的时间内加入一个物品，\(\mathcal{O}(V^2)\)的时间内合并两个背包，所以不妨设背包类型为多重背包。先考虑一个弱化版问题。给定一棵有根树，若一个节点被选，则它的父亲必须被选。显然存在一个\(\mathcal{O}(nV^2)\)的树形DP做法，它能求出以每个节点为根时其子树的答案。接下来引出科技：树上依赖性背包。我们发现对每个节点都求答案似乎有些累赘，因为我们只关心以\(1\)为根时的答案
题目传送门：https://www.luogu.com.cn/problem/P1073思路：首先，我们目的是想要在图上dp求最优的路线，但是原图上会存在环，那么我们就要先通过tarjan缩点，将所有环缩成一个点，同时，记录每个点的最大值和最小值，缩点得到DAG后，我们可以在DAG上进行dp，每次转移有三种方式，一是保留上一个点的dp值，二是求得目前所在点的值，三是这个点本身的dp值，三者取最大就ok了。还要注意的是，在建DAG图的时候，要记录每个点的入度，在之后的dp过程中，每一个点在全部走到的时候，才能压入队列，进行更新操作，保证dp内的值是最优的，也就是无后效性。代码：1#include
题目传送门：https://www.luogu.com.cn/problem/P1073思路：首先，我们目的是想要在图上dp求最优的路线，但是原图上会存在环，那么我们就要先通过tarjan缩点，将所有环缩成一个点，同时，记录每个点的最大值和最小值，缩点得到DAG后，我们可以在DAG上进行dp，每次转移有三种方式，一是保留上一个点的dp值，二是求得目前所在点的值，三是这个点本身的dp值，三者取最大就ok了。还要注意的是，在建DAG图的时候，要记录每个点的入度，在之后的dp过程中，每一个点在全部走到的时候，才能压入队列，进行更新操作，保证dp内的值是最优的，也就是无后效性。代码：1#include
本题为12月30日22寒假集训每日一题题解题目来源:(未知)题面题目描述懒羊羊和小灰灰在玩一种棋盘游戏，棋盘的尺寸为n个方格*m个方格。一开始在棋盘的右上角（1，m）放一枚硬币，每次一个人可以将硬币向左、下或左下的方格移动。当某个人无法再移动硬币了，那么这个人就输了。游戏总是懒羊羊先开始，如果他们两个每步都是最优策略，则谁将赢得游戏？输入输入包含多组测试数据。每组输入两个整数n和m（0当n=m=0时，输入结束。输出对于每组输入，如果懒羊羊赢，输出“Wonderful!”，否则输出“Whatapity!”。样例输入Copy53546600样例输出CopyWhatapity!Wonderful!W
本题为12月30日22寒假集训每日一题题解题目来源:(未知)题面题目描述懒羊羊和小灰灰在玩一种棋盘游戏，棋盘的尺寸为n个方格*m个方格。一开始在棋盘的右上角（1，m）放一枚硬币，每次一个人可以将硬币向左、下或左下的方格移动。当某个人无法再移动硬币了，那么这个人就输了。游戏总是懒羊羊先开始，如果他们两个每步都是最优策略，则谁将赢得游戏？输入输入包含多组测试数据。每组输入两个整数n和m（0当n=m=0时，输入结束。输出对于每组输入，如果懒羊羊赢，输出“Wonderful!”，否则输出“Whatapity!”。样例输入Copy53546600样例输出CopyWhatapity!Wonderful!W
Atcoder链接：CoinsLuogu链接：Coins$\scr{\color{BlueViolet}{Solution}}$观察数据，发现$\cal{n}\le3000$，说明$Ο(\cal{n^2})$可过,容易想到DP。用$\cal{dp[i][j]}$表示抛完第$\cal{i}$个硬币时，有$\cal{j}$个硬币正面朝上的概率。 考虑$\cal{dp[i][j]}$如何转移，易发现有以下两种情况，（当前正面朝上概率为$\cal{p_i}$）：本次抛得硬币是正面：抛到正面概率乘抛完第$\cal{i-1}$个硬币后，有$j-1$个硬币朝上的概率。本次抛得硬币是反面：抛到反面概率乘抛完第
Atcoder链接：CoinsLuogu链接：Coins$\scr{\color{BlueViolet}{Solution}}$观察数据，发现$\cal{n}\le3000$，说明$Ο(\cal{n^2})$可过,容易想到DP。用$\cal{dp[i][j]}$表示抛完第$\cal{i}$个硬币时，有$\cal{j}$个硬币正面朝上的概率。 考虑$\cal{dp[i][j]}$如何转移，易发现有以下两种情况，（当前正面朝上概率为$\cal{p_i}$）：本次抛得硬币是正面：抛到正面概率乘抛完第$\cal{i-1}$个硬币后，有$j-1$个硬币朝上的概率。本次抛得硬币是反面：抛到反面概率乘抛完第
前言今日偶然打开\(oi-wiki\)，发现树形\(DP\)例题正好是之前在洛谷上鸽着的一道题。所以......\(\color{red}{很高兴以这样的方式认识你，树形DP!}\)这例题造的太好了，简直是无痛入门（感动.jpg）P1352没有上司的舞会题目传送门~思路剖析状态定义\(dp_i\)表示的是以\(i\)为根节点的子树所获得的最大价值。由于每个节点代表着一位人物，有来与不来两种状态，所以再加一维状态变量。\(dp_{i,0}\)表示以\(i\)为根节点的子树所能获得的最大价值，且这位人物没来。\(dp_{i,1}\)则对应来了的状态。状态转移方程现在有个周年庆宴会，宴会每邀请来一个
前言今日偶然打开\(oi-wiki\)，发现树形\(DP\)例题正好是之前在洛谷上鸽着的一道题。所以......\(\color{red}{很高兴以这样的方式认识你，树形DP!}\)这例题造的太好了，简直是无痛入门（感动.jpg）P1352没有上司的舞会题目传送门~思路剖析状态定义\(dp_i\)表示的是以\(i\)为根节点的子树所获得的最大价值。由于每个节点代表着一位人物，有来与不来两种状态，所以再加一维状态变量。\(dp_{i,0}\)表示以\(i\)为根节点的子树所能获得的最大价值，且这位人物没来。\(dp_{i,1}\)则对应来了的状态。状态转移方程现在有个周年庆宴会，宴会每邀请来一个
