在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #石子合并#

本题针对于区间进行操作，是一个区间dp的问题。对于某个区间i,j能够得到的最大值等于在区间里面分成两部分中所有两部分的最大值。那么再看分出来的这两部分其实又可以划分两部分。那么动态规划的状态转移方程就出来了：dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][...

C++ 动态规划区间dp

2023-10-12

2 324

题解|#「木」迷雾森林#

某一个位置上的途径数其实源于左边和下面，也就是说某一个位置只来自左边和下边。那么动态方程就可以出来了。又有可以使用BFS来走这个地图所以在BFS的过程中加入动态规划记录累计的途径数就可以了。 #include <bits/stdc++.h> using ...

C++ 动态规划广度优先搜索

2023-10-11

1 357

题解 | #钉子和小球#

本题动态规划问题的状态转移很明显在小球下落的每一层里面发生变化，所以使用二维dp[i][j]来表示某一行某一个钉子或者去掉的钉子所拥有的小球。题目要求最后以分数的方式给出答案，那么我们可以以小球的数量比下手，小球每进过一次钉子就会分裂成两个，这样就去考虑他到达底部某个槽子里面有多少个小球，然...

C++ 动态规划

2023-10-11

1 369

题解 | #免费馅饼#

动态规划问题，用时间和水平方向的编号作为一个二维的状态。那么某个时间下某个水平编号所能够得到的最大的分数就是由上一个时间段的状态通过5种移动方式得到的。那么状态转移方程就出来了。因为没有涉及到的编号不存在所谓的转移，所以一开始将数组初始化成-1，判断如果等于-1的话直接跳过。对于路径：同样通...

C++ 动态规划

2023-10-10

1 366

题解|#花店橱窗#

是一个动态规划问题，不是背包问题，背包问题的特点在于有最优的值，而且有某种限制。在这里面需要将花插入花瓶当中，由于有所有的花束在放入花瓶时必须保持其标识数的顺序这个限制。所以应该最外层是以花作为遍历，这样可以保证这个顺序。那么动态转移方程为：dp[i][j]=max(dp[i-1][1~j-...

C++ 动态规划

2023-10-10

0 384

题解|#可爱の星空#

对于某个数量的星星来说，它的连同的最小代价应该是将其折半后拼接，那么折半后折半下来的其余部分也按照这样折半的思路去，之后全部相加就是最小的代价。 //以星星为第一维，那么每加入一个星星能够得到的代价作为二维。 #include <bits/stdc++.h> using&...

C++ 深度优先搜索动态规划

2023-10-10

0 568

题解 | #草药大师#

题目需要对dp进行优化来减少不需要的空间和时间，在这里我们使用map去保存，使用滚动数组去代替每一种草药。那么某一种草药对状态的影响就可以表示为去遍历map里面的每一个元素，拿这个元素的时间去加上这个时间，如果满足条件那么就可以去判断这将it->first+t这个时间下的最大值更新掉。...

C++ 动态规划 map优化超大背包

2023-10-09

1 352

题解 | #队伍配置#

本题从者和装备都只能使用一次，证明是一个01背包问题。但是条件中对于装备又受从者的限制，从者也最多只能有5个。除此之外还有cost值的限制。再加上每一个装备或者从者本身都就有4个东西需要去维护了。而对于装备或者从者本身可以使用滚动数组的方式不需要去创建一个数组维度。那么本题中装备的维度必须在...

C++ 动态规划 01背包二位费用背包 01背包 C++ 二位费用背包动态规划

2023-10-09

1 370

题解 | #[NOIP2006]金明的预算方案#

又看错题了。。。。。题目中所说的意思是一个一个主件最多能够有2个附件，这是在给数据的时候规定好的不是我们去控制的。所以在某种主件下最多就只有4中情况。那么将这四种情况枚举出来，那么就和分组背包是一模一样的问题了。分组背包：将组作为对外层循环，这样对于每个组选取哪一个就只和之前的那一组...

C++ 动态规划分组背包

2023-10-08

3 410

题解 | #多重背包#

首先可以将多重背包的每一种物品的数量都看做一种物品，这样就转化成了01背包。但是由于数据过大会超时。所以在这里采用二进制的优化，可以使用二进制将其某种物品的数量捆绑成1,2,4,8.。。。。。。这样可以将表示的数量缩短。然后采用01背包的做法即可。 #include &...

C++ 动态规划多重背包

2023-10-08

1 325