链接：Miku 这题没边界，用bfs比较好 与处理完了就没什么好说的特别之处 #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int safe[305][305]; i…

链接：Miku 这道题给了我一个惨痛的教训 虽然说我是被学信息学不用写字吸引的，但是做题必须证明，必须动笔证明！ 本蒟蒻被绿题卡了3个小时有感 这道题最后写出来发现并不是怎么很难啊，为了无后效性，我们倒着搜索每一个任务，因为任务的特殊要求，我们开一个数组记录这个时候的 开始的任务数。对于每一个时间，只有两种情况，有任务从这里开始或者没有，所以判断一…

链接：Miku 这道题的dp还是先更新子节点，在更新父节点，不过问题就是怎样更新他们 我们定义ff[i][j]为第i个节点字数上共保留j条边的情况下最多的苹果数，对于每一个点，他保留的边必然是他直接保留的之前保留的边和他当前儿子保留的边的值的和加上这一条边的 边权，即ff[u][i]=max(ff[u][i],f[u][i−j&minu…

链接：Miku 此文不是正解，而且主要内容都在代码和注释上 这是暴力分组背包做法 对于每一个主件及其附件，我们的选择是有限的，而且这道题中说了最多两个附件，那么 我们完全可以枚举每一种组合，然后组合成一件新的物品，并且属于同一个集合，然后对处理后的新物品们 跑分组背包就行了 #include<iostream> #include<…

链接：Miku 分组背包，我们只需要在01背包的基础上稍加修改，把同一类的物品同时枚举即可。 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m; …

链接：Miku 很入门的树形dp，首先，在这个题中，我们要做的就是求出来每一个子节点，然后用他们去更新父亲节点。 对于每一个节点，他有两种状态，去，或者不去，我们定义dp[i][0]为第i个节点也去的状态，而dp[i][1]为它不去，那么很显然 如果这个点去了，它的子节点肯定不去，那么dp[i][1]=dp[孩子们][0]的和， 如果这个点不去，它…

链接：Miku 这是一道dp题，我么很容易发现这点。 数据范围很大，如果直接用两个塔的高度当状态，很危险，我们就必须要考虑一下优化了。 两个塔的高度其实是没有没要的，我们追求的是差值，那么，比如6 8 和7 9，很明显，无论我们怎么放，第二个就是第一个加1，无论如何。 那么我们没必要存第一个状态的，很显然，第二个更优 我们定义方程 dp[i][j]…

链接：Miku 差分约束的可以算是例题吧，这道题我们要建立的约束系统是前缀和，毕竟要求的就是区间的和的最少的 最后，用前缀和求出总区间和就行了 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #incl…

链接：Miku --------------------------- 这道题本质上还是一个spfa板子，考虑一下题目的条件，到达一个城市后，肯定会赚到d的钱，那么我们把这个钱视为在路上赚的，然后到达一个城市 立即去下一个城市，其实是等价的，我们就把边权转换成了点权。 再考虑一下飞机，能赚的钱减去机票钱既可以了，是个负数？题目说了可以赊账。 一直赚…

链接：Miku 这道题本质上还是个st表，只要两个st表，然后对于每一个点，查询他开始的 长度为m的去年的最大值，最小值之差就可以了。 然而这个题还有个坑点，太大了，直接写会MLE，我们重新读一下题，题目说了区间是M。 那我们最多开到log2（m）就可以了，再大也用不到啊（这个小优化让它变成了绿题） 然后就可以AC了。 #include<io…