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

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

博客爬取于2020-06-14 22:43:44
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52289905

题目链接:http://codeforces.com/problemset/problem/710/E
-------------------------------------------------.
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
--------------------------------------.
题目大意 :
就是从0开始 每次可以+1或-1或*2 ±操作花费x *2操作花费y 问你达到n的最小花费是多少?

解题思路 :
就是DP
DP 的时候只要从0遍历到n即可 因为题目的数据范围是1e7 所以并不会超时
转移的时候一共决策三种状态 就是
1.由i-1 转移过来的
2.由i/2 转移过来的 这时候要区分下奇数还是偶数
——— 偶数很简单了 只要决策i 与 i/2 的状态就行了
——— 奇数的话 那么一定是前一个数2+1或者2-1达到的状态 由于遍历的时候已经判断了+1的情况 所以 这里只需考虑-1的情况就行 所以决策的事i 与 i/2+1

然后输出下结果就好了

附本题代码
-------------------------------------------.

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
# include <bits/stdc++.h>

using namespace std;

# define LL long long int
const int M = 1e7+7;
LL dp[M];
int main()
{
    ios::sync_with_stdio(false);
    LL n,x,y;
    while(cin>>n>>x>>y)
    {
        dp[0]=0,dp[1]=x;
        for(int i=2;i<=n;i++)
        {
            dp[i]=dp[i-1]+x;
            if(i&1) dp[i]=min(dp[i],dp[i/2+1]+y+x);
            else    dp[i]=min(dp[i],dp[i/2]+y);
        }
        printf("%I64d\n",dp[n]);
    }
    return 0;
}