CF1497E2 Square-free division (hard version)

我知道状态应该设计为dp (i,k)来表示当前转移到第i位,使用了k次机会。

但是有一个深深的困扰。

贪心地,我把改的数字枚举成了1,但我设计转移方程的时候,我是一个数一个数的讨论要不要加入的。

这样会出现bug:我可以用hash判断能不能加入,但没法实现修改这个功能,也就是说,假设我不能加入了,

但我选择了修改,改成1,那么在后面继续转移的时候,这个修改就没法起作用,因为我不可能记下每时每刻动态的序列。

题解的做法是枚举修改的区间,在使得它的转移是整段整段的,这样可以保证每次枚举都是从断点开始,k也好操作了。

那么时间会不会超时呢?

如果可以预处理出对于当前的这个点来说,往前修改x次后,可以得到的最远长度就好了。

记录修改x次后能一路往前直到j点。

那么答案是dp i,k=min ( dp i,k     ,dp j,k-x  +1  );

为什么要记最远?贪心~

枚举i,枚举k,复杂度大概是10五次方乘20;

预处理的操作其实也是一种dp。

如果当前数字能加入,就继承前一个,如果不能加入,就把自己改成1,消耗次数+1;

可能有点瑕疵,标解的做法是双指针,,

现在歌单放到了凤凰花开的路口,还有四季予你,我想到了几个在我生命里留下过痕迹但再也没有理由出现的人

完整的ac和报告待会吧。

 

但是,dp有奇奇怪怪的优化,顺序,预处理,综合题,这正是我喜欢它的地方,永远新鲜。

 

上一篇:CF1497E1 Square-free division (easy version)题解


下一篇:题解 Division Game