在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #大魔法师牛可乐#

本题得知道一个结论，如果序列里面的数的最大公约数为1的话就一定可以到达任意一个魔法阵。那么就对最大公约数进行动态规划。以每个数为外层循环。每一次都与前面有的或产生的数进行最大公约数的计算，然后更新某个数作为最大公约数所需要的花费即可。 //对于某一个数它的加入对原来产生的...

C++ 动态规划

2023-10-18

1 353

题解 | #宝藏猎人#

本题直接使用dfs，然后配合剪枝去接最好。直接dfs的去进行每一步当递归到最大的拥有宝藏的岛屿的下一个就可以宣布结束返回了。如何剪枝：本题中dfs是从前向后的传参形的记录当前的宝藏数量，那么如果某个岛屿第二遍被递归到的时候如果当前的宝藏数还没有之前的大。那么再递归下去就没有意义了。这...

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

2023-10-18

0 332

题解 | #货船#

使用二进制运算去优化01背包的循环过程可以。可以使用二进制去优化01背包的循环过程原因：在背包循环里面其实是针对于某一个物品判断如果他自身不取或者取能不能有一种是可以满足条件的。那么不取显而易见就是上一层循环的结果直接继承下来，取呢？取就得减去这个物品本身的重量，那么这个过程其实和序列整体左...

C++ 动态规划二进制优化01背包

2023-10-17

1 309

题解 | #To the Max#

求每个纵列的前缀和然后去遍历每个纵列。对于某一行来说可以使用在一维求最大序列和的做法，如果前一个最大总和小于0的话就直接取自身，如果大于0的话就加上。 #include <bits/stdc++.h> using namespace std; con...

C++ 动态规划

2023-10-16

2 232

题解 | #最大m个子段和#

从左向右看，对于i位置选出j个不相交连续字段，那么对于i位置来说就有两个选择：首先要知道的是我们所确定的区间里面的j个不相交的连续字段必须以i所在的字段结尾（因为如果不以i所在的字段结尾的话那在前面一定有结尾的下标，那本身就不应该是i这个区间了。） dp[i][j] = dp[i-1][j]+a[...

C++ 动态规划

2023-10-16

1 410

题解 | #迁徙过程中的河流#

从题目中规律可以看出来在某个人要过河的时候要么是最快的那个人来接她，要么是还剩下两个让最快的把船开回来然后让这两个过去，之后让第二快的把船开过来，全部过去。这两个在题目中的样例里面都有体现。 dp[i] = max(dp[i-1]+a[0]+a[i], dp[i-2]+a[0]+a[i]+a[...

C++ 动态规划

2023-10-15

1 329

题解 | #[NOIP2007]矩阵取数游戏#

//每次都要在每一层进行取，也就是说层与层之间没有什么关联。x,i和j是区间左右。 //dp[x][i][j] = max(dp[x][i+1][j]+pow(2,n)*a[i][j], dp[x][i][j-1]+pow(2,n)*a[i][j]); //每次都要在每一层进行取，也就是说层...

C++ 动态规划区间dp

2023-10-15

1 353

题解 | #合并回文子串#

字符串c中价值最大的子串一定是由A中的某个子串和B中的某个子串组成的。那么对于已知的dp[i][j][k][l]的状态，可以转移到取A字符串两边放到C字符串两边。可以是取B字符串两边放到C字符串两边。可以是取A字符串的右边和B字符串的左边来放到C字符串的两边可以是取A字符串左边和B字符串的右...

C++ 动态规划区间dp

2023-10-15

1 451

题解 | #田忌赛马#

本题首先看上去像是一个贪心问题，对于齐王的马从大到小进行排序，然后对于齐王的马来说如果田的马没有比齐王马好的，那么就使用田最弱的马和他去比。如果有比齐王好的马就去赢。但在这里面有反例的存在，如果平局的时候怎么办？是直接平局好还是输掉好？例如：1 2 3,1 2 3来说算平局就是0，那么就没...

C++ 动态规划区间dp

2023-10-14

4 488

题解 | #凸多边形的划分#

本题凸多边形要划分成三角形可以从定点和定边两个角度来看，从定点角度来看的话定一个点后，后两个点再去分隔所形成的的三个多边形并不是连续的区间。这样的话对于区间dp来说不好处理。但是从定边这个角度来看的话，定一条边后去选取另外一个点这样形成的一个区域一定是一个三角形，另外两个区域一定是一个连续的...

C++ 动态规划

2023-10-13

1 375