题目描述Elias Gamma\texttt{Elias Gamma}Elias Gamma编码是一种用于编码正整数序列的编码方法。本题使用一种修改后的版本可以编码零。编码一个整数nnn的原始规则是令kkk为nnn的二进制位数先写k−1k-1k−1个零然后写一个 1这部分称为前缀长度为kkk再写nnn的二进制表示长度为kkk因此一个整数nnn在原始编码下的总长度为2k2k2k。对于整数序列将每个整数的编码按顺序拼接即得整个序列的编码。本题允许两种优化操作前缀重映射如果某个前缀长度ppp对应的二进制长度ppp在原始序列中不存在即没有位数为ppp的整数则这个前缀可以用于表示一个更大的二进制长度bpb pbp的整数。此时前缀长度仍为ppp但后面跟随的二进制部分长度为bbb。加前导零可以把一个二进制长度为iii的整数前面添加若干个零使其二进制长度变为bib ibi从而它可以与更短的前缀匹配。通过合理组合这两种优化可以缩短整个序列的编码长度。输入给出nnn和c1,c2,…,cnc_1, c_2, \dots, c_nc1,c2,…,cn其中cic_ici表示二进制长度为iii的整数个数。要求输出最小可能的总编码长度。问题分析1. 核心观察首先注意到如果某种二进制长度iii在原始数据中根本没有出现ci0c_i 0ci0那么它对应的前缀长度iii的原始模式不会被任何整数使用因此可以被重新映射通过加前导零我们无法凭空创造出二进制长度为iii的整数因为加零只能使长度增加不能创造中间长度因此只有原始数据中实际出现的二进制长度才需要被编码。设这些长度为L1L2⋯LmL_1 L_2 \dots L_mL1L2⋯Lm对应的个数为cnt1,cnt2,…,cntmcnt_1, cnt_2, \dots, cnt_mcnt1,cnt2,…,cntm。题目中n≤128n \le 128n≤128但实际出现的种类mmm可能更少。2. 编码结构在最终编码中前缀长度必须从111开始连续使用解码器按顺序读取前缀。设我们使用了ppp个不同的前缀长度分别为1,2,…,p1, 2, \dots, p1,2,…,p。每个前缀iii会被分配给一个二进制长度LjL_jLj即该前缀后面跟随LjL_jLj位二进制数。由于前缀与二进制长度一一对应且解码时需要区分分配必须是单射。又因为前缀长度连续且LjL_jLj互不相同实际上我们是对出现的二进制长度进行了一个顺序分配第iii个前缀对应第jij_iji种长度且j1j2⋯jpmj_1 j_2 \dots j_p mj1j2⋯jpm最后必须覆盖所有mmm种长度。3. 区间覆盖模型假设第iii个前缀对应第jjj种长度LjL_jLj而前一个前缀第i−1i-1i−1个对应第kkk种长度LkL_kLkkjk jkj。那么前i−1i-1i−1个前缀已经覆盖了第1…k1 \dots k1…k种长度第iii个前缀需要覆盖第k1,k2,…,jk1, k2, \dots, jk1,k2,…,j种长度这些长度的整数通过加前导零全部统一为最终长度LjL_jLj每个这样的整数编码长度为前缀长度iii 最终二进制长度LjL_jLjiLji L_jiLj因此第iii个前缀覆盖的区间[k1,j][k1, j][k1,j]的代价为(iLj)×∑tk1jcntt (i L_j) \times \sum_{tk1}^{j} cnt_t(iLj)×tk1∑jcntt这是一个典型的区间覆盖DP\texttt{DP}DP将mmm种长度划分成若干连续段第ppp段对应前缀ppp覆盖[l,r][l, r][l,r]代价为(pLr)×(p L_r) \times(pLr)×区间整数个数总代价最小化。4. 动态规划状态设计设dp[i][j]dp[i][j]dp[i][j]表示已经使用了前缀长度1…i1 \dots i1…i且第iii个前缀对应第jjj种二进制长度LjL_jLj时覆盖前jjj种长度的所有整数所需的最小总编码长度。边界条件dp[0][0]0dp[0][0] 0dp[0][0]0表示未使用任何前缀时覆盖000种长度。转移方程dp[i][j]min0≤kj{dp[i−1][k](iLj)×∑tk1jcntt} dp[i][j] \min_{0 \le k j} \left\{ dp[i-1][k] (i L_j) \times \sum_{tk1}^{j} cnt_t \right\}dp[i][j]0≤kjmin{dp[i−1][k](iLj)×tk1∑jcntt}这里k0k 0k0表示前一个状态尚未覆盖任何长度必须满足i≤ji \le ji≤j因为至少需要iii种不同的长度才能分配iii个前缀实际编程时kkk的起始值取max(0,i−1)\max(0, i-1)max(0,i−1)因为第i−1i-1i−1个前缀至少对应第i−1i-1i−1种长度否则无法满足i−1i-1i−1个不同的二进制长度最终答案ansmin1≤i≤mdp[i][m] ans \min_{1 \le i \le m} dp[i][m]ans1≤i≤mmindp[i][m]5. 复杂度状态数O(m2)O(m^2)O(m2)转移O(m)O(m)O(m)总复杂度O(m3)O(m^3)O(m3)。由于m≤n≤128m \le n \le 128m≤n≤1281283≈2×106128^3 \approx 2 \times 10^61283≈2×106完全可行。代码实现// Elias Gamma Coding// UVa ID: 11632// Verdict: Accepted// Submission Date: 2026-05-30// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintINF1e9;intmain(){intn;while(cinn,n){vectorintc(n1);for(inti1;in;i)cinc[i];// 提取实际出现的二进制长度vectorintL,cnt;for(inti1;in;i)if(c[i]0){L.push_back(i);cnt.push_back(c[i]);}intmL.size();// 前缀和便于快速计算区间整数个数vectorintpre(m1,0);for(inti1;im;i)pre[i]pre[i-1]cnt[i-1];// dp[i][j]: 用了 i 个前缀最后一个前缀对应第 j 种长度vectorvectorintdp(m2,vectorint(m2,INF));dp[0][0]0;for(inti1;im;i){for(intji;jm;j){// k 是前一个前缀对应的种类至少为 i-1保证有 i-1 个不同长度intstartK(i1)?0:i-1;for(intkstartK;kj;k){if(dp[i-1][k]INF)continue;intsumpre[j]-pre[k];// 区间 [k1, j] 的整数个数dp[i][j]min(dp[i][j],dp[i-1][k](iL[j-1])*sum);}}}intansINF;for(inti1;im;i)ansmin(ans,dp[i][m]);coutansendl;}return0;}总结本题的关键在于发现只有原始数据中实际出现的二进制长度才需要处理将问题转化为区间覆盖 前缀分配的DP\texttt{DP}DP模型每个前缀覆盖一个连续区间区间内所有整数统一提升到右端点长度使用dp[i][j]dp[i][j]dp[i][j]表示用iii个前缀覆盖前jjj种长度的最小代价这种模型也可以推广到其他类似的前缀码优化问题中。
