文和906

分类

未归档(4) 项目笔记(5) 题解(103)

/ 注册

全部文章（共3篇）

题解 | #nico和niconiconi#

典型的线性动态规划。使用前缀和的思路，建立一个数组用于存储字符串str前i个字符中最大的值，然后寻找其递推关系。显然，每遍历一个字符，都要判断其前i个字符中最大的前缀和的a, b, c的状态，有可能仅是增加1个a, b, c，亦有可能增加3个a，减少一个c。最后，前缀和数组中的末项即为整个字符串最大...

C++ 线性动态规划

2021-10-27

0 470

题解 | #不相邻取数#

开始时使用暴力法，用一个三重循环枚举出所有可能的不相邻数的和，并选出其中最大的和作为输出其核心思想是对每一种可能的间隔，每一种可能的起点，计算出其最大的和。由于数组元素非负，所以在起点与间隔固定的情况下，数字当然越多越好。具体做法为，最外层循环控制间隔，间隔是从1~size()-2的。中间层循环控制...

C++ 线性动态规划

2021-10-27

0 669

题解 | #子数组最大连续和#

从头遍历输入数组，先假设数组中元素不全为负。每次都将当前元素加到sum中，然后判断，sum，若sum<0，则令sum=0。因为之后sum必定已经加到或将会加到一个不为负的数。若sum>max，则令max=sum。然后对数组全为负的情况添加一些判断。此时max必定为负，则当sum<0...

C++ 线性动态规划

2021-10-27

0 455