mengbierr

一个蒟蒻的博客

12月23

Atcoder CADDi2018 E.Negative Doubling

题目描述

给出n个正整数,你可以每次对一个数乘-2,问最少多少次操作能使这些数单调递增。

题解

显然应该让这些数先是一些负数,然后是一些正数,那么问题变成选一个位置,前面的数先乘-2,然后让前面的数单调递减,后面的数单调递增。将顺序颠倒后,前面和后面的解决方法相同。
先考虑后面部分的解决方法,可以发现,一个位置的操作次数超过15,那么每次再对这个位置操作,就要对后面的所有位置操作。
定义f[i][j]表示考虑i-n的数,对i位置上操作j次后满足条件的需要操作的最少次数,然后转移即可。
之后枚举分界点求答案。

发表评论

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