在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #免费馅饼#

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

C++ 动态规划

2023-10-10

1 365

题解|#花店橱窗#

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

C++ 动态规划

2023-10-10

0 383

题解|#可爱の星空#

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

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

2023-10-10

0 567

题解 | #草药大师#

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

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

2023-10-09

1 351

题解 | #队伍配置#

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

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

2023-10-09

1 369

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

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

C++ 动态规划分组背包

2023-10-08

3 409

题解 | #多重背包#

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

C++ 动态规划多重背包

2023-10-08

1 324

题解 | #[NOIP2018]货币系统#

本题是一个完全背包问题，但需要将题目中的问题进行转换。题目中要求最小的等价货币系统的m值。那么其实就是求原有的货币序列里面有哪些数是可以被其他数表示出来的，那么这些数就是不必要存在的数。又有肯定是小的数可以组合成大的数，所以可以首先对序列进行一个排序。然后对于数的排除其实就相当于某个数可以用...

C++ 动态规划完全背包

2023-10-08

1 443

题解 | #Steadily Growing Steam#

这题和失衡天平 (nowcoder.com)这道题很像，都是天平两端需要放东西，那么就把必然需要去维护一个天平两端重量差。但是这道题还有一个技能的使用，使用技能可以将点数加倍。所以这个技能的使用也得需要维护。那么就是维护一个技能的使用次数。 //将手上的牌分成两部分，如果两部分点数相同那么就得...

C++ 动态规划 01背包

2023-10-08

3 387

题解 | #失衡天平#

动态规划问题。确定状态：在某物品要产生的重量差的数值能够放多少重量取决于这个物品会放到天平中的那一边或轻的那一边或不放。有这三种情况之后产生的差值就是上一个物品产生的差值中能够放物品的最大值了。那么递推式为：dp[i][j] = max(dp[i-1][j+a[i]]+a[i], ...

C++ 动态规划

2023-10-08

1 445