ACM题解:多段子段和
把过去和现在的笔记记录也搬了过来,也算是给以后留个念想吧,想想一开始打acm就是图一乐,后来发现这游戏还挺上头的,也算是度过了一段电竞生涯(xs)
早些时候的笔记写的好中二,连我自己看着都羞耻。
不过,就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目,以DP为主,非DP的题目都用※进行了标识。
当然,有些题解思路本身也是源自其他人的,不过除非特殊标注,否则都是用的自己的代码。
12 Etudes Op.25:No. 11 in A minor - Winter Wind
00:00 / 00:00
An audio error has occurred.
- 1 12 Etudes Op.25:No. 11 in A minor - Winter Wind
题目大意:
给N个数,求m个不相交子段的最大段和,每个子段大小不限。
解:
熟悉线性DP的人很快就会发现,这其实就和普通的最大子段和没什么区别。
普通子段和的状态转移为:对于a[i],选择将其加入其之前的子段或不加入。
多段子段和则是:对于a[i],选择将其加入上一个序号为j的子段或是自己作为第j个子段段头,注意是上一个,因此在空间不够的时候可以直接上滚动数组。
DP[i][j]表示共有j段,结尾为i时的最大子段和,写法上有些细节,但是都没什么影响,唯一有影响的是在遍历第j个子段的子段头时要从第j个数开始。
如果一定要有m段(也就是每段长度都大于0)的话取DP[n][m],否则要取max(DP[n][k])。
久违地放个代码,只是因为还存着而已,才不是为了你写的呢。
代码
cpp
1 |
|
此文章版权归EmiteInna所有,多看看吧。