Code-Festival-2017-qualA_____F - Squeezing Slimes

AtCoder

已知一个若干个1构成的序列，然后每次可以选择2n个连续的数，按照(1,2)(3,4),...(2n-1,2n)的方式合并，得到最终的序列。现在告诉你最终的序列，求最少几步。

官方题解说构造三元组，然后证明了其一定是最优的
然后DP解决
editorial(1).pdf297.3kB

感觉非人类

感觉这个说的还靠谱一些

显然应该倒过来做。那么考虑一次操作就是把连续的若干>1的数拆成两半，显然应该贪心地拆成均匀的两份。

再考虑题解里DP的过程，确实均分才是最少的构造步数

#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;
}