在刷题的单身狗很开心

题解

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

/ 注册

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

题解 | #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 403

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

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

C++ 动态规划

2023-10-15

2 324

题解 | #[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 457

题解 | #田忌赛马#

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

C++ 动态规划区间dp

2023-10-14

4 459

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

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

C++ 动态规划

2023-10-13

1 384

题解 | #石子合并#

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

C++ 动态规划区间dp

2023-10-12

2 325

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

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

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

2023-10-11

1 352

题解 | #钉子和小球#

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

C++ 动态规划

2023-10-11

1 363