526互联

Educational Codeforces Round 16 E

发布时间 2023-11-29 00:09:45作者: ycllz

提炼
首先观察范围发现是1e7 好像是dp
但是发现直接朴素的dp发现是有环的
跑了一发dijk带log 答案是肯定没过
我们可以想一下
如果我要是一个10 我肯定不会从11转移过来 因为我不如先去5 再2
如果我要是一个9 我可以从8+1转移过来 也可以从52-1转移过来
这样我们就消除了环

int dp[20000010];
void solve(){
    int n,x,y;cin>>n>>x>>y;
    memset(dp,0x3f3f,sizeof dp);
    dp[1]=x;
    for(int i=2;i<=n;i++){
        if(i%2==0){
            dp[i]=min({dp[i],dp[i/2]+y,dp[i-1]+x});
        }else{
            dp[i]=min({dp[i],dp[i/2+1]+x+y,dp[i-1]+x});
        }
    }
    cout<<dp[n]<<endl;
}