在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #购物#

动态规划问题，一开始看到每天要买的糖果数还不一样，而且每个糖果还有他自己不同的价格。直接就想到了状压DP。但本题要求花费最小，而对于某一天买k个糖果来说花费最小其实就是从价格低的糖果来买就行了。那么某一天如何选糖果的问题就这样简答的解决了。那么状态数组为：dp[i][j]。i代表天数...

C++ 动态规划

2023-11-16

1 372

题解 | #逛公园#

本题要求求路径数，图论的最短路算法可求不了路径数，那么可以想到在图里面使用动态规划的方式去求路径数。在本题里面可以得出从某一点到下一点的路径方式有多少取决去这一点之前的路径数，以及该点和下一点的路径数。那么就可以知道之间可以使用动态规划去求解。但本题有要求路径长度不能超过n+...

C++ 动态规划迪杰斯特拉算法图论最短路径

2023-11-16

2 400

题解 | #Rinne Loves Graph#

//迪杰斯特拉算法配合上动态规划 //动态规划的数组为：dp[i][j]。表示到达第i号城镇，穿过了k次所走的最短路 //一定要注意迪杰斯特拉将优先队列里面已经作为最短判断过了不要再判断了。否则会发生很奇怪的错误。 #include <bits/stdc++.h> using&...

C++ 图论动态规划迪杰斯特拉算法

2023-11-02

1 368

题解 | #[NOIP2003]加分二叉树#

二叉树？？树状dp？？NONONO！！！本题的树不固定，他要求去找出来一个最优的树，所以不适合使用树状dp去进行求解。但又因为题中所给的有中序遍历的序列，中序遍历序列最大的特点在于定根可将区间分成左右子树。那么分成两部分之后就可以分别去计算这两部分，也就是在这两小部分里面取找根。那...

C++ 动态规划区间dp

2023-10-29

1 382

题解 | #树学#

在树上进行操作的记忆化搜索，通过DFS加灵活换根的方式进行。首先先走一遍DFS，得到每个节点下的深度和，节点的个数和（包括节点自身）。然后让1成为根，那么再进行DFS下去的每一个节点都可以有一个动态规划递推式来快速计算得到加入某个节点为根的时候的深度和。递推式为：dp[x] ...

C++ 动态规划记忆化搜索

2023-10-29

1 300

题解 | #打砖块(brike)#

很折磨的一道题除了要进行转换以外，还要十分注意每层循环的范围。解释不了一点，直接挂一个我觉得写的比较好的博客吧。 (*´∇｀*) 欢迎回来！ (cnblogs.com) //首先矩阵旋转90度，去除后效性。 //f[i][j][k]表示截止到第i行，总共已经选j个砖块，...

C++ 动态规划变形动态规划

2023-10-29

1 493

题解 | #[SCOI2009]粉刷匠#

//分组背包问题，首先考虑一个木板的情况： //对于一个木板而言：dp[i][j]，i表示当前是第i次粉刷，粉刷第j块格子的情况。 //那么得到状态转移方程为：dp[i][j] = max(dp[i-1][l]+num[l+1][j])。 //其中num[l+1][j]表示在l到...

C++ 动态规划分组背包

2023-10-28

1 397

题解 | #Min酱要旅行#

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

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

2023-10-28

1 418

题解 | #[NOIP2008]传纸条#

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

C++ 动态规划

2023-10-27

0 335

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

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

C++ 动态规划

2023-10-26

1 320