【题解】洛谷P1880 [NOI1995]石子合并

题目

洛谷P1880石子合并

题解

这是一道经典的区间dp题,f[l][r]表示将区间[l,r]之间的石子合并后的最值。可以由长度小的区间推得长度大的区间的信息。题中数据是环状的,需要断环为链,将原序列复制并加到后面。

代码

Subscribe
提醒
guest
3 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年9月13日 下午4:43

【小白解析】
此题解法较简明易懂。需注意f1/f2[l][r]代表合并[l,r]区间完毕后的最小/最大值,故18和19行的操作中,+sum[r]-sum[l-1]的造作本意是将已经合并完成的[l,k]和[k+1,r]所累积的分数,再加上合并这两堆的分数。
*话说第4行的200+5究竟是个啥啊……

cyx
cyx
Reply to  Martin
2020年9月13日 下午4:58

为毛不直接写205啊(恼)