在刷题的单身狗很开心

题解

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

/ 注册

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

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

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

C++ 动态规划区间dp

2023-10-29

1 383

题解 | #[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的问题。对于某个区间i,j能够得到的最大值等于在区间里面分成两部分中所有两部分的最大值。那么再看分出来的这两部分其实又可以划分两部分。那么动态规划的状态转移方程就出来了：dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][...

C++ 动态规划区间dp

2023-10-12

2 324