@zzzc18
2017-09-28T15:38:20.000000Z
字数 1085
阅读 1277
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;
}