cf_710_E

此文更新于2019.6.22

你最开始有一个0，要构造出n
你有两种操作，
    1 加上或减去一代价为x
    2 乘以2 代价为y
数据范围
    n<1e18
    x<1e9
    y<1e9

dp[i] -> 构造出n的最小代价
i为偶数 dp[i] <- dp[i-1] , dp[i/2]
i为奇数 dp[i] <- dp[i-1] , dp[i/2+1]

// #include
// using namespace std;

// typedef long long ll;
// const ll maxn=2e7+7;
// ll d[maxn];

// struct node{
// ll n,step;
// bool operator <(const node&rhs) const{
// return step>rhs.step;
// }
// };

// int main(){
// ll n,x,y;
// scanf("%lld%lld%lld",&n,&x,&y);
// for(ll i=0;i<=2*n;i++) d[i]=1e18;
// priority_queue q;
// d[1]=x;
// q.push(node{1,x});

// ll ans=x*n;
// while(true){
// node top=q.top(); q.pop();
// ans=min(ans,d[]+);
// if(top.n==n) break;
// else{
// if(top.n-1>=1&&d[top.n]+x
// d[top.n-1]=d[top.n]+x;
// q.push(node{top.n-1,d[top.n]+x});
// }
// if(top.n+1<=2*n&&d[top.n]+x
// d[top.n+1]=d[top.n]+x;
// q.push(node{top.n+1,d[top.n]+x});
// }
// if(top.n*2<=2*n&&d[top.n]+y
// d[top.n*2]=d[top.n]+y;
// q.push(node{top.n*2,d[top.n]+y});
// }
// }
// }
// cout<
// }

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll maxn=2e7+7;
ll dp[maxn];

int main(){
    ll n,x,y;
    scanf("%lld%lld%lld",&n,&x,&y);
    for(int i=1;i<=n;i++){
        if(i&1){//odd
            dp[i]=min(dp[i-1]+x,dp[(i+1)/2]+y+x);
        }
        else{
            dp[i]=min(dp[i-1]+x,dp[i/2]+y);
        }
    }
    cout<<dp[n]<<endl;
}

此文标签
dp优化转移方程

cf_710_E

cf_710_E

谢谢大爷~