头像
guaoxiang
发布于 2019-11-04 21:45
+ 关注

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了


全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐