图像压缩动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
* 首先，要知道：像素点存储的位数（bit）=log2(像素点的个数)+1。1<=像素点的个数<=255。其中log(像素点的个数)向下取整
* 例:将像素序列表示成数组p[n]={10,9,12,40,50,35,15,12,8,10,9,15,11,130,160,240}。
* 像素点存储的最大位数=log2(255)+1=8。（优先选取最大的位数为其他像素点个数存储的基准）
* 因此可以选择都用8bit存储，这样一共消耗16*8=128bit的空间
* 观察p[1]=10，log2(10)+1=4；p[2]=log2(9)+1=4；p[3]=log2(12)+1=4......p[16]=log2(16)+1=8。
* 可以构造新的数组q[n]={4,4,4,6,6,6,4,4,4,4,4,4,4,8,8,8}记录每个位置像素点存储所需要的最少bit。
* 直接都按8bit存储虽然消耗更多的空间在，但在计算机内部指令之间的转换不需要做的查找位置的操作。
* 这里，如果这样划分	4 4 4|6 6 6|4 4 4 4 4 4 4|8 8 8,并不是说消耗的空间就是4*3+6*3+4*7+8*3=82bit。
* 就像从中文翻译成英文，可以直接翻译，一个中文对应的一个英文单词。但是从英文翻译成中文，如果对英语单词陌生，并且该单词一词多义，
* 就会出现错误翻译的情况。这里缺少相关的位置信息，因此并不能做到在A和B之间的相互转化。
* 因此需要额外消耗空间去记录相关的信息。
* 题目已经给出提示了，可以用b[j]表示划分的某一段中像素点的位数，l[j]表示划分的这一段的长度。
* 还是按	4 4 4|6 6 6|4 4 4 4 4 4 4|8 8 8划分,可以得到
*			 4 3 | 6 3 |     4 7     | 8 3 
* 题目规定1<=b[j]<=3,1<=l[j]<=8，因此最大消耗额外的记录信息的空间是3+8=11,把这个作为固定值。（我也不太懂为什么这么规定）
* 因此这样划分所占的空间为(11+4*3)+(11+6*3)+(11+4*7)+(11+8*3)=126bit。
* 但是这并不是最优解。
* 最优的划分方案为	4 4 4 6 6 6|4 4 4 4 4 4 4|8 8 8
*                     6(6>4，所以选择6) 6|4 7  | 8 3
* 所占的空间为(11+6*6)+(11+4*7)+(11+8*3)=121bit
* 
* 设计转移方程：f[i]表示考虑从第1个像素点到第i个像素点所消耗最少的bit。
* 当不进行划分时,f[i]=max[q[1],q[i]*i]+11。
* 当1<=k<i时，f[k]已经是考虑过的最优解了，需要将剩下的k+1到i,即i-k个像素点划分为一类，这一部分消耗的内存为max[q[k+1],q[i]]*(i-k)+11。
* [q[k+1],q[i]]表示区间。因此f[i]=f[k]+max[q[k+1],q[i]]*(i-k)。题目要求每个分段长度不得超过256，f[0]=0
* 因此f[i]=min(f[k]+max[q[k+1],q[i]]*(i-k)),0<=k<min{i,256}。
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using UI = unsigned int;
UI log2(UI num);
vector<UI> p = { 10,9,12,40,50,35,15,12,8,10,9,15,11,130,160,240 };
int main()
{
	vector<UI>q;
	int n = (int)p.size();
	for (int i = 0; i < n; i++)
		q.push_back(log2(p[i])+1);
	UI* f = new UI[n + 1]{ 0 };
	for (int i = 1; i <= n; i++)
	{
		f[i] = UINT_MAX;
		int limit = min(i, 256);
		for (int k = 0; k < i; k++)
		{
			UI maxbit;
			if(i!=n)
				maxbit = *max_element(q.begin()+k, q.begin()+i);
			else
				maxbit= *max_element(q.begin() + k, q.end());
			f[i] = min(f[i], f[k] + maxbit * (i - k) + 11);
		}
	}
	cout << f[n] << endl;
	delete[] f;
	return 0;
}

UI log2(UI num)
{
	if (num == 1)
		return 0;
	if (num == 2 || num == 3)
		return 1;
	if (num >= 4 && num <= 7)
		return 2;
	if (num >= 8 && num <= 15)
		return 3;
	if (num >= 16 && num <= 31)
		return 4;
	if (num >= 32 && num <= 63)
		return 5;
	if (num >= 64 && num <= 127)
		return 6;
	if (num >= 128 && num <= 255)
		return 7;
	else
		return -1;
}