题意:
分析:
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int l[N], b[N];
int f[N];
int calc(int x) {
int cnt = 0;
while(x) {
cnt ++;
x /= 2;
}
return cnt;
}
void dp() {
for (int i = 1; i <= n; i ++) {
b[i] = calc(a[i]);
l[i] = 1;
int bit_max = b[i];
f[i] = f[i - 1] + bit_max;
for (int j = 2; j <= min(i, 256); j ++) {
bit_max = max(bit_max, b[i - j + 1]);
int val = f[i - j] + j * bit_max;
if (val < f[i]) {
f[i] = val;
l[i] = j;
}
}
f[i] += 11;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
dp();
cout << f[n] << endl;
return 0;
}
Q.E.D.