@zzzc18 2017-09-28T15:38:20.000000Z 字数 1085 阅读 1212

# Code-Festival-2017-qualA_____F - Squeezing Slimes

AtCoder

editorial(1).pdf297.3kB

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const LL MAXN = 200000+9;LL n;LL a[MAXN];struct DATA{    LL k,pd;}num[MAXN];LL dp[MAXN][2];LL ans;DATA cal(LL x){    LL i;LL pos;    for(i=1,pos=0;i<=x;i<<=1,pos++);    i>>=1;    if(i==x){        return (DATA){pos-1,0};    }    else{        return (DATA){pos,1};    }}void solve(){    LL i;    for(i=1;i<=n;i++){        num[i]=cal(a[i]);       }    for(i=1;i<=n;i++)        ans+=num[i].k;    for(i=2;i<=n;i++){        dp[i][0]=max(dp[i][0],dp[i-1][0]+min(num[i-1].k-num[i-1].pd,num[i].k));        dp[i][0]=max(dp[i][0],dp[i-1][1]+min(num[i-1].k,num[i].k));        dp[i][1]=max(dp[i][1],dp[i-1][0]+min(num[i-1].k-num[i-1].pd,num[i].k-num[i].pd));        dp[i][1]=max(dp[i][1],dp[i-1][1]+min(num[i-1].k,num[i].k-num[i].pd));    }    printf("%lld\n",ans-max(dp[n][0],dp[n][1]));}int main(){    scanf("%lld",&n);    LL i;    for(i=1;i<=n;i++)        scanf("%lld",&a[i]);    solve();    return 0;}

• 私有
• 公开
• 删除