mengbierr

一个蒟蒻的博客

1月24

bzoj3427: Poi2013 Bytecomputer

可以发现,最后剩下的数一定由-1,0,1,组成。

证明:如果有一个位置上的数>1,则这个数一定在之前能变成1,如果下一位是-1,需要至少两次才能满足条件,而0,1,需要1次,这和当前位是1的效果是1一样的,所以猜想得证。

然后就dp求就可以了,转移很简单。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注