数字编码

题目链接：None

题目大意

有一些数组，你可以把它按顺序分成一定的段数，一段长度不可以到 256 或以上。
每段的费用是 12+数组个数*最大的数的二进制位数。
求最小总费用。

思路

我们考虑 DP。

$f_i$ 为处理出前 $i$ 个数的最小费用。
你就从后往前枚举 $j$，然后 $j+1\sim i$ 作为新的一段，它的费用加上 $f_j$，取最小的那个就是 $f_i$。

由于一段长度顶多 $255$，我们 $j$ 最多只用往后 $255$ 个，时间是过得去的。

然后为什么要从后往前呢？因为这样我们可以顺便维护出你新加的那一段最大数，和它的位数是多大。
每个数的位数可以预处理一下，稍微缩小时间。

代码

#include<cstdio>
#include<cstring> 
#include<iostream>
#define ll long long

using namespace std;

int n, b[30001];
int a[30001], x;
ll f[30001];

int main() {
//	freopen("coding.in", "r", stdin);
//	freopen("coding.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		x = a[i];
		if (x == 0) {
			b[i] = 1;
			continue;
		}
		while (x) {//预处理每个数是多少位的
			b[i]++;
			x >>= 1;
		}
	}
	
	memset(f, 0x7f, sizeof(f));
	f[0] = 0;
	for (int i = 1; i <= n; i++) {
		int maxn = b[i], size = 1;
		for (int j = i; j >= 1 && size < 256; j--) {
			f[i] = min(f[i], f[j - 1] + 1ll * size * maxn);//计算
			maxn = max(maxn, b[j - 1]);//维护这堆数中位数最大
			size++;//维护长度
		}
		f[i] += 12;//记得加一组费用要+12
	}
	
	printf("%lld", f[n]);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}