CCF 压缩编码 100分

小咪咪 2023-07-18 11:15 23阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td>试题编号：</td> 
 <td>201612-4</td> 
 </tr> 
 <tr> 
 <td>试题名称：</td> 
 <td>压缩编码</td> 
 </tr> 
 <tr> 
 <td>时间限制：</td> 
 <td>3.0s</td> 
 </tr> 
 <tr> 
 <td>内存限制：</td> 
 <td>256.0MB</td> 
 </tr> 
 <tr> 
 <td>问题描述：</td> 
 <td> 问题描述 　　给定一段文字，已知单词a1, a2, …, an出现的频率分别t1, t2, …, tn。可以用01串给这些单词编码，即将每个单词与一个01串对应，使得任何一个单词的编码（对应的01串）不是另一个单词编码的前缀，这种编码称为前缀码。 　　使用前缀码编码一段文字是指将这段文字中的每个单词依次对应到其编码。一段文字经过前缀编码后的长度为： 　　L=a1的编码长度×t1+a2的编码长度×t2+…+ an的编码长度×tn。 　　定义一个前缀编码为字典序编码，指对于1 ≤ i &lt; n，ai的编码（对应的01串）的字典序在ai+1编码之前，即a1, a2, …, an的编码是按字典序升序排列的。 　　例如，文字E A E C D E B C C E C B D B E中， 5个单词A、B、C、D、E出现的频率分别为1, 3, 4, 2, 5，则一种可行的编码方案是A:000, B:001, C:01, D:10, E:11，对应的编码后的01串为1100011011011001010111010011000111，对应的长度L为3×1+3×3+2×4+2×2+2×5=34。 　　在这个例子中，如果使用哈夫曼(Huffman)编码，对应的编码方案是A:000, B:01, C:10, D:001, E:11，虽然最终文字编码后的总长度只有33，但是这个编码不满足字典序编码的性质，比如C的编码的字典序不在D的编码之前。 　　在这个例子中，有些人可能会想的另一个字典序编码是A:000, B:001, C:010, D:011, E:1，编码后的文字长度为35。 　　请找出一个字典序编码，使得文字经过编码后的长度L最小。在输出时，你只需要输出最小的长度L，而不需要输出具体的方案。在上面的例子中，最小的长度L为34。 输入格式 　　输入的第一行包含一个整数n，表示单词的数量。 　　第二行包含n个整数，用空格分隔，分别表示a1, a2, …, an出现的频率，即t1, t2, …, tn。请注意a1, a2, …, an具体是什么单词并不影响本题的解，所以没有输入a1, a2, …, an。 输出格式 　　输出一个整数，表示文字经过编码后的长度L的最小值。 样例输入 5 1 3 4 2 5 样例输出 34 样例说明 　　这个样例就是问题描述中的例子。如果你得到了35，说明你算得有问题，请自行检查自己的算法而不要怀疑是样例输出写错了。 评测用例规模与约定 　　对于30%的评测用例，1 ≤ n ≤ 10，1 ≤ ti ≤ 20； 　　对于60%的评测用例，1 ≤ n ≤ 100，1 ≤ ti ≤ 100； 　　对于100%的评测用例，1 ≤ n ≤ 1000，1 ≤ ti ≤ 10000。 </td> 
 </tr> 
 </tbody> 
</table>

思路解析：首先这个题我第一想法是用哈夫曼树找出所有哈夫曼编码，然后把哈夫曼编码按照字典序排序，按照顺序分配给ABCDE，这样ABCDE的编码就是按照字典序的了，而且哈夫曼树得到的值最小，但是这样想是错误的，这样依然不能保证题目中所有编码长度的最小。下面进行正确的分析：

首先我们肯定是要用ABCDE进行建树的，但是在建树的过程中，ABCDE的相对位置不能改变，也就是说只能两个相邻的字母进行合并，合并之后的字母还是放在原来的位置。

根据题目举例：ABCDE的出现频率分别是 1, 3, 4, 2, 5。

我们第一次只能合并1和3 或者 3和4  或者 4和2 或者 2和5。

如果我们合并的是1和3、2和5，我们会得到：4、4、7。

然后第二次只能合并4和4 或者 4和7。

如果我们合并的是4和4，我们会得到：8，7

最后我们合并8和7。

这样我们的树就建立好了。题目中有一个共式：***L*=*a*1的编码长度×*t*1+*a*2的编码长度×*t*2+…+ *an*的编码长度×*tn*。**

我们字母a1的总编码长度就等于**a1的编码长度xa1的出现频率t1。**

其实a1的编码长度就等于a1所在的节点经过的合并次数(也就是a1节点所在的树的层数-1)。

所以我们字母a1的总编码长度也等于**a1所在的节点经过的合并次数xa1的出现频率t1**。

### 这种问题类似**石子问题，****可以用****动态规划**。 ###

下面讲一下这个题动态规划的思路：

我们假设dp\[i\]\[j\]表示的是第i个节点到第j个节点所建立的子树的最小权重，子树的权重就等于子树中单个字母的权重总和。

单个字母的权重等于该字母的出现频率乘以它所在的节点经过的合并次数。

dp\[i\]\[j\]就等于dp\[i\]\[k\] + dp\[k+1\]\[j\]+从i到j所有字母的频率和（因为现在要把从i节点到k节点合并得到的子树和从k+1节点到j节点合并得到的子树再合并，所以每个节点的合并次数都会加1，每个节点对应的权重也就再加上自己的出现频率）。（i=<k<=j）。

其中k的位置是从i到j，选一个最佳的。

也就是dp\[i\]\[j\]就等于min(dp\[i\]\[k\] + dp\[k+1\]\[j\]+从i到j所有字母的频率和)（i=<k<=j）。

dp\[i\]\[i\] = 0。因为这个时候它所在的节点经过的合并次数为0，它还是一个单独的节点，没有经过合并。

#include<iostream>
 #include<algorithm>
 using namespace std;
 const int MAXN = 1002; 
 
 int cnt[MAXN];
 int sum[MAXN];
 int dp[MAXN][MAXN];
 
 int main(){
 	int n;
 	cin>>n;
 	for(int i=1;i<=n;i++){
 		cin>>cnt[i];
 		sum[i] = sum[i-1] + cnt[i];
 	}
 	
 	//dp
 	for(int len=2;len<=n;len++){
 		for(int i=1;i+len-1<=n;i++){
 			int j = i+len-1;
 			for(int k=i;k<j;k++){
 				if(!dp[i][j]){
 					dp[i][j] = dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
 				}else{
 					dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);					
 				}
 			}
 		}
 	}
 	
 	cout<<dp[1][n]<<endl;
 	return 0;
 }

另外我自己写了好久的用哈夫曼树求哈夫曼编码的代码也给出来，虽然这个题这样用是错的，但是求哈夫曼编码的过程没错。我不定以后自己会看。

#include<bits/stdc++.h>
 #include<iostream>
 #include<algorithm>
 #include<string>
 #include<vector>
 #include<queue>
 using namespace std;
 const int MAXN = 1002; 
 const int INF = 999999;
 
 //树节点 
 struct TreeNode{
 	int id; //当前节点在数组中的下标 
 	int w; //出现频率 
 	int lc,rc; //lc:左孩子在数组中的下标; rc:右孩子在数组中的下标。 
 	TreeNode(){}
 	TreeNode(int id,int w){
 		this->id = id;
 		this->w = w;
 		this->lc = -1;
 		this->rc = -1;
 	}
 };
 
 //存储在优先队列中的节点 
 struct QueNode{
 	int id; //当前节点在数组中的下标 
 	int w; //出现频率 
 	QueNode(){}
 	QueNode(int id,int w){
 		this->id = id;
 		this->w = w;
 	}
 	bool operator<(const QueNode &node) const { //重载小于号 
 		return this->w >= node.w;
 	}
 };
 
 TreeNode tree[MAXN]; //存储哈夫曼树 
 int index = -1; //哈夫曼树对应数组的最后一个元素的下标 
 priority_queue<QueNode> heap; //存储所有节点，包括由初始节点合并而成的节点，按照出现频率对节点进行排序。方便树的创建。 
 vector<string> code; //存储哈夫曼编码 
 
 void createTree(){
 	while(heap.size() >= 2){
 		//选择两个出现频率小的节点进行合并。 
 		QueNode qnode1 = heap.top();
 		heap.pop();
 		QueNode qnode2 = heap.top();
 		heap.pop();
 		index++;
 		//把合并后的新节点加入到优先队列中 
 		heap.push(QueNode(index,qnode1.w + qnode2.w));
 		//把合并后的新节点加入到树对应的数组中 
 		TreeNode tnode(TreeNode(index,qnode1.w + qnode2.w));
 		tnode.lc = qnode1.id;
 		tnode.rc = qnode2.id;
 		tree[index] = tnode;
 	}
 }
 
 vector<int> path;
 void showTree(int root,int type){
 	TreeNode tnode = tree[root];
 	if(tnode.lc == -1){ //到达叶子节点 
 		path.push_back(type);	
 		string temp = "";
 		//type为-1的情况下的push_back不算入，所以i从1开始
 		for(int i=1;i<path.size();i++){ 
 			temp.append(to_string(path[i]));
 		}
 		code.push_back(temp);
 		path.pop_back();
 		return ;
 	}
 	path.push_back(type);	
 	showTree(tnode.lc,0); //0--左节点 
 	showTree(tnode.rc,1); //1--右节点 
 	path.pop_back();
 }
 
 int main(){
 	int n;
 	int temp;
 	cin>>n;
 	for(int i=1;i<=n;i++){
 		cin>>temp;
 		tree[i] = TreeNode(i,temp);
 		heap.push(QueNode(i,temp));
 	}
 	index = n;
 	createTree();
 	showTree(index,-1);
 	sort(code.begin(),code.end()); //按照字典序排序 
 	int ans = 0;
 	for(int i=0;i<code.size();i++){
 		ans += code[i].length() * tree[i+1].w;
 	}
 	cout<<ans<<endl;
 	return 0;
 }