codeforces-710E-Generate a string-基础dp

题意：让你生成一个长度为n的字符串，字符串仅包含字母a，已知单独输入或删除一个字符的时间为x，复制当前串并粘贴的时间为y,现让你求最短需要多长时间才能生成

思路：最基础的dp,考虑当前字符为2k的情况，那么只有两种转移，一个是复制k长度的字符，一个是从2k-1添加。当前字符为2k+1的情况时，有三种情况，一个是从2k转移，一个是从k乘2加1转移，最后一个是从（k+1）乘2减1转移。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long dp[10000007];
int main()
{
   long long sum,x,y;
   long long n;
   scanf("%lld%lld%lld",&n,&x,&y);
   dp[0]=0;
   dp[1]=x;
   for(int i=2;i<=n;i++)
   {
   	if(i%2==0)dp[i]=min(dp[i/2]+y,dp[i-1]+x);
   	else
   	{
   	 long long temp1=dp[i/2]+y+x;
   	 long long temp2=dp[i/2+1]+y+x;
   	 dp[i]=min(dp[i-1]+x,temp1);
   	 dp[i]=min(dp[i],temp2);
	   
	}
   }
   printf("%lld\n",dp[n]);
   return 0;   	
 }