Codeforces ER16 710E

正文索引 [隐藏]

传送门:http://codeforces.com/problemset/problem/710/E

题目翻译

产生一个长度为n的全a字符串,增加/删除一个a消耗x时间,倍长当前字符串消耗y时间,求最短时间。

题解

可以发现,这是一个DP。然而删除操作并不是很方便DP。
我们仔细思考,发现减法的情况只可能在翻倍字符串之后出现一次。
首先我们不可能先添加一个字母再删除一个字母。
其次如果翻倍字符串需要两次减法,我们可以在翻倍之前做一次减法,这样次数更优。
综上,只有两种情况。当前需要产生n个字符时。
如果n为偶数,我们比较F[n/2]+y , F[n-1]+x
如果n为奇数,我们比较F[(n+1)/2]+x+y , F[n-1]+x

代码