在刷题的单身狗很开心

题解

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2)

/ 注册

全部文章 / 题解（共53篇）

题解 | #mixup2混乱的奶牛#

本题算是状压dp的一个变形用法，在这里面将二进制位上的数从0变到1其实做得将牛放到末尾的操作，那么可以看到对于某一头牛他只关心前面一头牛是什么，前面牛到底有几种摆放方式和当前的牛无关。这符合动态规划的特性。那么很容易得到状态转移方程为：dp[state|(1<<(i-1))][i...

C++ 动态规划状压dp

2023-10-26

2 285

题解 | #Most Powerful#

本题状压dp的简单应用，用0表示还没有消失或没有被使用的气体，1表示已经使用的气体。每次枚举寻找两个气体，饭后将其中一个变成1就行。 //在这里我们直接使用一维状态的转移，这样在转移的过程中去挑选值为0的两个节点 //那么这两个节点肯定有一个留下来，我们假设删除的节点为j，那么就有 //...

C++ 动态规划状压dp

2023-10-26

1 251

题解 | #郊区春游#

本题从众多郊区里面选取R个郊区，要求走过一遍之后的中距离最短，那么我们首先就是要得到R个郊区彼此之间的最短距离，然后根据这个最短距离再来安排怎么走合适。那么要求彼此之间的最短距离问题就得用到数据结构里面学到的弗洛伊德算法了，根据弗洛伊德算法将所有的最短距离求出来。那么问题就回归到了经...

C++ 动态规划状压dp 最短路算法弗洛伊德算法

2023-10-25

2 445

题解 | #炮兵阵地#

本题算是[SCOI2005]互不侵犯KING (nowcoder.com)这道题的升级版，在互不侵犯这道题里面除了同一行的限制，上下行的限制仅仅包含一行。而在这道题里面则是包含了两行。那么我们可以像互不侵犯那样将状态转移数组设成dp[i][j]，i表示某一层，j表示当前层的二进制数吗？当然不...

C++ 动态规划状压dp

2023-10-24

2 332

题解 | #[SCOI2005]互不侵犯KING#

本题需要在N*N个棋盘里面摆放上K个国王，国王需要互不侵犯。那么从这个矩阵的角度来看（果断dfs[赞]）（开玩笑的。本题使用状压dp去求解，以每一层作为最外层遍历取走，对于每一层来说哪些格子上放的有国王就是1，没有放国王就是0，所以直接采用二进制去表示每一层的状态。而到某一层为止到底...

C++ 动态规划状压dp

2023-10-24

2 268

题解 | #树上子链#

本题的树上子链的说法是我第一次见，树上子链指的是树上的任意一条链，换句话说就是树上任意两点中最长的那一个。但这题不是以长度定的，每个节点都有权值，要的是权值和最长的子链。所以我们对于某一个节点，选取儿子中最长和次长。然后加上节点本身就是答案了。但在这里面寻找最长和次长的方式很巧妙，先...

C++ 动态规划树形dp

2023-10-22

1 417

题解 | #二叉苹果树#

本题中很大不同点在于他给的是边的数值，而正常的树的问题是在节点上给值。那么我们采用边值下放点的做法，这样就是正常的树问题了。那么对于某一个节点来说它保留j个节点所得到的最大苹果树取决于这j个节点来自于左边子树多少，来自右边子树多少。又因为他自身就有一个节点所以状态转移方程为： &nbs...

C++ 动态规划树形dp

2023-10-22

1 383

题解 | #[USACO 2008 Jan G]Cell Phone Network#

本题是点的最小覆盖集问题，是一个树形dp问题。对于某一个节点来说他能通信来自于他父亲以及他儿子节点以及他自身。那么dp[n][3]表示某个节点三这种情况下的最小值。 0：靠父亲。 1：靠自己。 2：靠儿子。那么对于靠自己和靠父亲来说很简单的能写出状态转移方程： ...

C++ 动态规划数形dp

2023-10-20

2 356

题解 | #没有上司的舞会#

题目中的意思翻译过来其实是在一颗数上相邻的节点只能选择一个，那么最大的和为多少。那么对于每一个节点来说就有选与不选两种状态：dp[i][0/1] 如果选的话那么以这个节点为根的子树最大和为：dp[i][1] = (f[i]+(所有子树和)dp[u][0]); 如果不选的话那么对于子树来说就有选...

C++ 动态规划树状dp

2023-10-19

1 289

题解 | #小G有一个大树#

对于某个节点来说，如果该节点删除那么就会形成他儿子节点全部独立成一棵树和他父亲节点的那棵树。那么状态转移方程：dp[i] = (total-f[i], (所有儿子节点最大的那个)f[u]) 对于求某个节点下有多少节点来说是一个简答树状dp问题。 f[i] = 1+(所有儿子节点)f[u]; ...

C++ 动态规划树状dp

2023-10-19

1 367