代码

/*
这个摸底考试突然变得好难... 
100%?0%?
*/

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

typedef long long uint64;

const int MAXN = 100000;
const int LOG = 20;
const uint64 INF = 1e14;

uint64 f1[LOG + 10], f2[LOG + 10];
uint64 a[MAXN+10];
int n;

int main() {
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
	
	int i, j;
	uint64 res=INF; 
	uint64 asum=0, bsum=0;
	
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%llu", &a[i]);
		asum+=a[i];
		bsum+=int(log2(a[i])); 
	}
	
	for(i=1; i<=LOG; i++) f2[i]=INF;
	f2[0]=0;
	for(i=1; i<=n; i++) {
		asum-=a[i];
		bsum-=int(log2(a[i]));
		for(j=0; j<=LOG and j<=i; j++) {
			f1[j]=f2[j]+a[i]*(1<<j);
			if(j) f1[j]=std::min(f1[j], f2[j-1]+int(log2(a[i]))+j-1);
			if(i^n and f1[j]^INF){
				res=std::min(res, f1[j]+asum*(1<<j));
				res=std::min(res, f1[j]+bsum+(uint64)(j+j+n-i-1)*(n-i)/2);
			}
		}
//		printf("%llu\n", res);
		memcpy(f2, f1, sizeof(f1));
	}
	
	printf("%llu\n", res);
	return 0;
}

// j, j+1, ..., j+(n-i-1)
// 0..n-i-1
// (j+j+n-i-1)*(n-i)/2

评测结果