T2

dp[k]表示把前k个分成若干组,这时候他后面都已经加上了,应该多加的数。

就是dp[k]=ans_k+x(组数)*sum_ans(k+1,n);

dp[k]->dp[i]

Ask(l,r)代表l到r的最大值减去最小值 用st搞出来

Ans_sum/sum_ans都代表前缀和

Cost(l,r)代表l到r的ask+sum。

方法一:数学推导

Dp[k]=ans_k+x(组数)*sum_ans(i+1,n)+x*sum_ans(k+1,i);

Dp[i]=ans_i+ans_sum(i+1,n)*(x+1)

=ans_k+ans_sum(k+1,i)*(x+1)+ask(k+1,i)+ans_sum(i+1,n)*(x+1)

=dp[k]+ans_sum(k+1,i)+ask(k+1,i)+ans_sum(i+1,n)

=dp[k]+cost(k+1,i)+ans_sum(i+1,n);

方法二:

瞪眼法

多加了cost(k+1,i)

更新后面+sum_ans(i+1,n);

dp[i]=dp[k]+sum_ans(i+1,n)+cost(k+1,i);

 优化 n*logn

实际上就是在找min(dp[k]+cost(k+1,i))+一个定值。

Cost非递减,dp要是再增,肯定不行

从i-1开始维护一个dp是递减的序列。

A了


全部评论
qwq。。。。。因为。。。。。。。傻了
点赞 回复 分享
发布于 2019-11-05 16:14
为什么不打lateX呢qwq
点赞 回复 分享
发布于 2019-11-05 15:11

相关推荐

不愿透露姓名的神秘牛友
07-03 17:37
点赞 评论 收藏
分享
06-14 19:09
门头沟学院 Java
darius_:给制造业搞的,什么物料管理生产管理,设备管理点检,最最关键的就是一堆报表看板。个人觉得没啥技术含量都是些基本的crud,但是业务很繁琐那种
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 14:10
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务