Educational Codeforces Round 16 E. Generate a String dp

题目链接：

http://codeforces.com/problemset/problem/710/E

E. Generate a String

time limit per test 2 seconds
memory limit per test 512 megabytes #### 问题描述 > 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. #### 输入 > 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. #### 输出 > Print the only integer t — the minimum amount of time needed to generate the input file. #### 样例 > **sample input** > 8 1 1 > > **sample output** > 4

题意

加减1的消耗是x，乘2的消耗是y，问通过这三个操作把0变成n的最小消耗

题解

贪心+dp
能证明的是偶数都不可能由后面的减回来的，所以即使是奇数也只能由后面的那个偶数减回来，而那个偶数就不用考虑后面再减了。
所以有转移方程：
i是偶数： dp[i]=min(dp[i/2]+y,dp[i-1]+x)
i是奇数： dp[i]=min(dp[i/2+1]+x+y,dp[i-1]+x)

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf

typedef __int64 LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=1e7+10;

LL dp[maxn];
int n,x,y;

int main() {
    scf("%d%d%d",&n,&x,&y);
    dp[1]=x;
    for(int i=2;i<=n;i++){
        if(i&1){
            dp[i]=min(dp[i-1]+x,dp[i/2+1]+y+x);
        }else{
            dp[i]=min(dp[i/2]+y,dp[i-1]+x);
        }
    }
    prf("%I64d
",dp[n]);
    return 0;
}

//end-----------------------------------------------------------------------

划分阶段，然后先处理乘2,再处理乘加，再处理乘减。（但是感觉还是在偶数不可能通过更大的数减回来的这个结论的基础上做的，可能没有理解清楚吧。。）

阶段1:1~2（dp[1]=x,dp[2]=min(x,y))
阶段2:2~4
...
阶段m：n~n*2

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf

typedef __int64 LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;

const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);

//start----------------------------------------------------------------------

const int maxn=2e7+10;

LL dp[maxn];
int n,x,y;

int main() {
    clr(dp,0x3f);
    scf("%d%d%d",&n,&x,&y);
    dp[1]=x;
    dp[2]=min(x+dp[1],y+dp[1]);
    for(int cur=2;cur<=n;cur<<=1){
        for(int i=cur;i<=cur*2;i++){
            if(i%2==0) dp[i]=min(dp[i],dp[i/2]+y);
            dp[i]=min(dp[i],dp[i-1]+x);
        }
        for(int i=cur*2;i>=cur;i--){
            dp[i]=min(dp[i],dp[i+1]+x);
        }
    }
    prf("%I64d
",dp[n]);
    return 0;
}

//end-----------------------------------------------------------------------