图像压缩

2023-08-30   


题意:

txys

分析:

代码:

#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.