在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #Min酱要旅行#

本题如果想要直接去求的话需要对每一个物品去掉的情况进行一个01背包，这样的代价太大全部都会超时的。那么我们将动态规划式子转换一下，某个物品去掉，背包容积在j下的种类数=背包容积在j下的种类数-某个物品一定要带，背包容积在j下的种类数。那么某个物品一定要带的情况，其实相当于背包容积在j...

C++ 动态规划 01背包动态规划问题转换

2023-10-28

1 419

题解 | #[NOIP2008]传纸条#

双线动态规划问题，双线代表有两个状态在同时进行改变，并且互相会影响。在本题中正反两个方向的传字条其实是一致的，也就是说从小轩到小渊的路径其实可以转化成从小渊到小轩的路径。这样可以将双线过程的起点保持一致。然后我们设状态数组为：其中i,j代表小渊纸条的坐标，k,l表示小...

C++ 动态规划

2023-10-27

0 336

题解 | #[ZJOI2007]棋盘制作#

本题使用悬线法。针对于每一点来说，他向上能到多长取决于上一个点的情况，如果上一个点与他相反那就h[i][j] = h[i-1][j]+1，否则的话就是 1。那么对于每一个点左边最长是多少，右边最长是多少都能求出来。然后我们可以看到在竖直方向会产生许多悬线，那么接下来去取这些悬...

C++ 动态规划

2023-10-26

1 321

题解 | #Mondriaan's Dream#

本题讨论的是每一行的矩形的摆放，而一开始因为纠结于将一个矩形用一个二进制表示，但矩形摆放的方式不同每一行的数位也就不同所以思路就此卡住了。。。。。。但我们从矩形的摆放方式将其定义成1和0，并且每一个边长为1的小格都有一个0或1，这样就保证了每一层二进制位数的相同，那么这样写的状态转移方程是什...

C++ 状压dp

2023-10-26

1 348

题解 | #mixup2混乱的奶牛#

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

C++ 动态规划状压dp

2023-10-26

2 284

题解 | #Most Powerful#

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

C++ 动态规划状压dp

2023-10-26

1 251

题解 | #简单环#

//动态规划数组依旧是：dp[state][j];i表示状态，j表示在当前状态下的结尾节点。 //但不同的在于这道题要找简单环，而对于找简单环来说定起点和终点是比较重要的。 //因为只有知道了起点和终点，然后又知道起点和终点是否有一条直接的线连接，就证明是不是环。 //如果我们单纯的去执行状态转移方...

C++ 状压dp

2023-10-26

2 377

题解 | #郊区春游#

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

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

2023-10-25

2 444

题解 | #炮兵阵地#

本题算是[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