[原创]codeforces 710E Generate a String [dp]【动态规划】

2016-08-23 12:49:21 Tabris_ 阅读数：585

https://blog.csdn.net/qq_33184171/article/details/52289905

-------------------------------------------------.
E. Generate a String
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
zscoder wants to generate an input file for some programming competition problem.

His input is a string consisting of n letters ‘a’. He is too lazy to write a generator so he will manually generate the input in a text editor.

Initially, the text editor is empty. It takes him x seconds to insert or delete a letter ‘a’ from the text file and y seconds to copy the contents of the entire text file, and duplicate it.

zscoder wants to find the minimum amount of time needed for him to create the input file of exactly n letters ‘a’. Help him to determine the amount of time needed to generate the input.

Input
The only line contains three integers n, x and y (1 ≤ n ≤ 107, 1 ≤ x, y ≤ 109) — the number of letters ‘a’ in the input file and the parameters from the problem statement.

Output
Print the only integer t — the minimum amount of time needed to generate the input file.

Examples
input
8 1 1
output
4
input
8 1 10
output
8
--------------------------------------.

DP 的时候只要从0遍历到n即可 因为题目的数据范围是1e7 所以并不会超时

1.由i-1 转移过来的
2.由i/2 转移过来的 这时候要区分下奇数还是偶数
——— 偶数很简单了 只要决策i 与 i/2 的状态就行了
——— 奇数的话 那么一定是前一个数2+1或者2-1达到的状态 由于遍历的时候已经判断了+1的情况 所以 这里只需考虑-1的情况就行 所以决策的事i 与 i/2+1

-------------------------------------------.