【HAOI2006】数字序列

Source and Judge

HAOI2006
luogu2501

Record

2h

Analysis

请先思考后再展开

目前本题一大堆人都是抄个n3方的代码完事(似乎难以证明复杂度),在此给出满n方的做法

使a递增等价于让bi=ai-i不递减
第一问就是让不改变的最少,直接总长-最长不递减子序列
然后第二问要求在第一问的前提下计算代价

结论:一定存在一种最优的区间调整方案,使得存在一个k,k左边和bj一样,右边和bi一样
证明:
首先对于能转移的j到i,之间的数要么比i大,要么比j小
想象一下最后连续的值为一个横线,那么每个x坐标相当于有个橡皮筋在拉着横线往bi方向走
那么如果最后的情况不是只有两段,那么总有木板往想去的方向,然后路上某个瞬间和【能任意上下的木板】合并
这样最后总是只有两段的

那么先设中间所有人变成bi的代价为old,然后考虑一个分界点k,额外的代价= $(big_{left}-small_{left})*(b_i-b_j)$
那么对于每个i,先预处理出$(big_{left}-small_{left})$的前缀和,然后倒序枚举j统计old即可

如果你仅仅是想ac本题,随便加点优化应该就行了

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/e4c.html
转载请注明出处,谢谢!