关于区间DP的额外链接 https://blog.csdn.net/qq_40831340/article/details/83478132 北京2014 icpc https://blog.csdn.net/qq_40831340/article/details/82714715 题目 石子合并 题目链接 https://www.luogu.org/problemnew/show/P1880 dp[i][j] 表示i-j区间的合并最优解 dp[i][j]={可以合并的区间+当前合并的代价} 在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新...

https://www.luogu.org/problemnew/show/P1280 f[i]表示1到i个时间最大空闲值。 本题是一道资源分配类动态规划。我们可以划分阶段的标准是时间和任务。如果尼克在一个时间点上没有接到任务，我们就让他延续他原来的空闲时段，现在空闲时间=上一个空闲点的空闲时间+1；如果这时有这个时间点开始的任务，我们就将其插入，有多个这样的任务供我们选择最优的。因为这个时间点尼克只有两个选择要么完成一个任务要么什么都不干，以开始时间来选择每一次都可以找到一个最优的。但是本题好在开始时间和完成时间都有一个严格的限定，所以我们可以不用考虑一个任务插入在哪个时间结束，只要根据开...

https://www.luogu.org/problemnew/show/P1280 f[i]表示1到i个时间最大空闲值。 本题是一道资源分配类动态规划。我们可以划分阶段的标准是时间和任务。如果尼克在一个时间点上没有接到任务，我们就让他延续他原来的空闲时段，现在空闲时间=上一个空闲点的空闲时间+1；如果这时有这个时间点开始的任务，我们就将其插入，有多个这样的任务供我们选择最优的。因为这个时间点尼克只有两个选择要么完成一个任务要么什么都不干，以开始时间来选择每一次都可以找到一个最优的。但是本题好在开始时间和完成时间都有一个严格的限定，所以我们可以不用考虑一个任务插入在哪个时间结束，只要根据开...

https://www.luogu.org/problemnew/solution/P1064 有依赖背包的入门题 除了树形DP 就是这了 非树形有依赖的背包问题（只有两类物品：主件，附件）有主件才可以选附件 首先我们注意到对于每一个主件，有很多种购买的方案：可以不买，可以只买主件，或者买主件外加几种附件，当附件个数较少的时候枚举就可以过 但我们正解的话，可以先对每种主件的 附件的集合 进行一次 01 背包处理，就可以先求出 对于每一种主件包括其附件的组合中，每种花费的最大价值 #include <iostream> #include <cstdio> #incl...

https://www.luogu.org/problemnew/solution/P1064 有依赖背包的入门题 除了树形DP 就是这了 非树形有依赖的背包问题（只有两类物品：主件，附件）有主件才可以选附件 首先我们注意到对于每一个主件，有很多种购买的方案：可以不买，可以只买主件，或者买主件外加几种附件，当附件个数较少的时候枚举就可以过 但我们正解的话，可以先对每种主件的 附件的集合 进行一次 01 背包处理，就可以先求出 对于每一种主件包括其附件的组合中，每种花费的最大价值 #include <iostream> #include <cstdio> #incl...

https://vjudge.net/problem/22741/origin 依旧是 树上对各个结点子树的操作 原题翻译： 有一家公司有N个员工(从1到N)，公司里每个员工都有一个直接的老板(除了整个公司的领导)。如果你是某人的直接老板，那个人就是你的下属，他的所有下属也都是你的下属。如果你是没有人的老板，那么你就没有下属，没有直接老板的员工就是整个公司的领导，也就是说N个员工构成了一棵树。公司通常把一些任务分配给一些员工来完成，当一项任务分配给某个人时，他/她会把它分配给他/她的所有下属，换句话说，这个人和他/她的所有下属在同一时间接受了一项任务。此外，每当员工收到一个任务，他/她将停止当...

https://vjudge.net/problem/22741/origin 依旧是 树上对各个结点子树的操作 原题翻译： 有一家公司有N个员工(从1到N)，公司里每个员工都有一个直接的老板(除了整个公司的领导)。如果你是某人的直接老板，那个人就是你的下属，他的所有下属也都是你的下属。如果你是没有人的老板，那么你就没有下属，没有直接老板的员工就是整个公司的领导，也就是说N个员工构成了一棵树。公司通常把一些任务分配给一些员工来完成，当一项任务分配给某个人时，他/她会把它分配给他/她的所有下属，换句话说，这个人和他/她的所有下属在同一时间接受了一项任务。此外，每当员工收到一个任务，他/她将停止当...

http://poj.org/problem?id=3321 题意 给你一颗树 Q是查询某个结点带他子树 的和 C 是改变树上结点 原来是0 变为1 原来1变为0 这样只需要 与或运算 ^ 就好了 而且单点更新 区间查询 水题 这道题重点是DFS对树建序 这样就可以更方便维护树和子树了 这里我DFS建序维护的是 结点应该管理的区间左右结点的序号 #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring>...

http://poj.org/problem?id=3321 题意 给你一颗树 Q是查询某个结点带他子树 的和 C 是改变树上结点 原来是0 变为1 原来1变为0 这样只需要 与或运算 ^ 就好了 而且单点更新 区间查询 水题 这道题重点是DFS对树建序 这样就可以更方便维护树和子树了 这里我DFS建序维护的是 结点应该管理的区间左右结点的序号 #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring>...

https://vjudge.net/problem/15201/origin 然后图上有不能到的点（墙），起点扔一个球，球只能砸到墙才能停止，但是砸到墙上之后，这个墙就没了，最多可以砸10次，扔出界就算输，能不能把这个球从起点扔到终点。 注意，要是该点紧挨着就是一个墙，那就不能往这个墙的方向上扔。 一开始想用广度优先搜索的，但是因为要每次撞完之后墙就消失了，所以感觉还是深度优先级写起来方便一些，要使用bfs的话，有可能到一个点用相同的步数但是有不同的扔法，这就导致了两种办法消失的墙不一样。总是实现起来是够麻烦的 然后 超时了 这地对深度有一个限制 显然DFS 不怕炸了 不过我还是写了发BF...

https://vjudge.net/problem/15201/origin 然后图上有不能到的点（墙），起点扔一个球，球只能砸到墙才能停止，但是砸到墙上之后，这个墙就没了，最多可以砸10次，扔出界就算输，能不能把这个球从起点扔到终点。 注意，要是该点紧挨着就是一个墙，那就不能往这个墙的方向上扔。 一开始想用广度优先搜索的，但是因为要每次撞完之后墙就消失了，所以感觉还是深度优先级写起来方便一些，要使用bfs的话，有可能到一个点用相同的步数但是有不同的扔法，这就导致了两种办法消失的墙不一样。总是实现起来是够麻烦的 然后 超时了 这地对深度有一个限制 显然DFS 不怕炸了 不过我还是写了发BF...

http://acm.hdu.edu.cn/showproblem.php?pid=2821 这题的题意是真的难看懂 给若干个可重叠的格子，起点可以任意选择，可以往四个方向一直走到有格子的地方为止，每碰一次就消掉一个格子，并且把剩下的移到下一个位置 如果能够位置有格子就累加。 注意：①起点不能有格子。②必须要隔一个位置才能碰。③碰的格子在边上时，剩下的格子不能移出矩形范围。④碰的最后部分格子在边上时，如果有剩余，初始位置就放错了 另找 #include <iostream> #include <cstdio> #include <cmath> #incl...

http://acm.hdu.edu.cn/showproblem.php?pid=2821 这题的题意是真的难看懂 给若干个可重叠的格子，起点可以任意选择，可以往四个方向一直走到有格子的地方为止，每碰一次就消掉一个格子，并且把剩下的移到下一个位置 如果能够位置有格子就累加。 注意：①起点不能有格子。②必须要隔一个位置才能碰。③碰的格子在边上时，剩下的格子不能移出矩形范围。④碰的最后部分格子在边上时，如果有剩余，初始位置就放错了 另找 #include <iostream> #include <cstdio> #include <cmath> #incl...

https://vjudge.net/problem/12685/origin 1.玩家从原点(0,0)出发 2.有流星在一定时间里往地图上砸。砸到以后，这个点以及上下左右共5个点就再也不能行走了(砸以前可以走) 3.玩家每个单位时间必须要上下左右走一格，只能在第一象限中移动 4.找到最短的行走距离，保证这个点是安全的，即所有流星都不会砸到这个点 // 不一定要离开300x300的范围 让我楞了好一会 // 重复打击的点 更新最小值就好 预处理啊预处理 怎么就楞住了呢 这么水的题 楞住了// 翻译完 一直在楞 不知道楞什么呢 #include <iostream> #inclu...