UVa 12451 Let‘s call SPaDe a SPaDe

题目描述给定一个由小写字母{a, b, c, d}构成的字符串SSS5≤∣S∣≤1005 \le |S| \le 1005≤∣S∣≤100可以对其进行一级压缩将任意连续子串用(X)k的形式表示其中XXX是任意非空字符串kkk是重复次数k≥2k \ge 2k≥2并且压缩不能嵌套即压缩后的串中不能再包含( ... )结构。我们的目标是通过这样的压缩使得最终表示的长度字符个数尽可能小并输出这个最小长度。例如abababab可以压缩为(ab)4长度为555括号两个字符子串ab两个字符数字4一个字符相比原长度888节省了333个字符。输入格式第一行包含一个整数TTT1≤T≤1001 \le T \le 1001≤T≤100表示测试用例数。接下来TTT行每行一个字符串SSS长度满足5≤∣S∣≤1005 \le |S| \le 1005≤∣S∣≤100。输出格式对于每个测试用例输出一行一个整数表示SSS经过一级压缩后可达到的最小长度。样例输入2 abcda dabbababbabadddddccccbbbbbbbbbbbb输出5 23第二个样例中最优压缩为d(abba)2ba(d)5cccc(b)12其长度为11412214122231 1 4 1 2 2 1 4 1 2 2 231141221412223具体长度计算见说明。题目分析本题的核心是给定一个长度不超过100100100的字符串允许将其划分为若干段每段要么保持原样要么表示成(X)k的形式XXX为一段子串kkk为重复次数且k≥2k \ge 2k≥2。压缩不能嵌套所以每个压缩块是独立的块之间直接拼接。由于∣S∣|S|∣S∣很小我们可以用动态规划DP\texttt{DP}DP解决。设dp[i]\textit{dp}[i]dp[i]表示前缀S[0…i−1]S[0 \ldots i-1]S[0…i−1]压缩后的最短长度。转移时考虑最后一个块若最后一个块为原样字符则dp[i]dp[i−1]1\textit{dp}[i] \textit{dp}[i-1] 1dp[i]dp[i−1]1若最后一个块是一个压缩块即S[j…i−1]S[j \ldots i-1]S[j…i−1]可以表示为(X)k(X)k(X)k则dp[i]min⁡(dp[i],dp[j]cost(j,i))\textit{dp}[i] \min(\textit{dp}[i], \textit{dp}[j] \text{cost}(j, i))dp[i]min(dp[i],dp[j]cost(j,i))其中cost(j,i)\text{cost}(j, i)cost(j,i)为将该子串压缩后的长度。问题转化为对于任意子串S[j…i−1]S[j \ldots i-1]S[j…i−1]判断它是否可以表示为某个字符串XXX重复kkk次k≥2k \ge 2k≥2并计算压缩后的长度。如果能则其压缩长度为2∣X∣digits(k)2 |X| \text{digits}(k)2∣X∣digits(k)括号两个字符XXX的长度以及kkk的十进制位数。注意若子串长度小于444即p⋅k≤3p \cdot k \le 3p⋅k≤3压缩不可能更短因为2∣X∣digits(k)≥21142 |X| \text{digits}(k) \ge 2 1 1 42∣X∣digits(k)≥2114而原长最多为333所以这样的压缩没有意义但我们的算法仍可处理实际上不会优。由于∣S∣≤100|S| \le 100∣S∣≤100我们可以直接枚举所有可能的周期ppp即XXX的长度和重复次数kkk计算每个子串的最小压缩代价然后进行DP\texttt{DP}DP。解题思路预处理所有子串的最小压缩代价定义一个二维数组cost[j][i]\textit{cost}[j][i]cost[j][i]表示子串S[j…i−1]S[j \ldots i-1]S[j…i−1]压缩后的最短长度。若该子串不能被压缩即不存在ppp使得它是某个字符串重复kkk次且k≥2k \ge 2k≥2则cost[j][i]∞\textit{cost}[j][i] \inftycost[j][i]∞。枚举过程枚举起点jjj0≤jn0 \le j n0≤jn。枚举周期ppp1≤p≤(n−j)/21 \le p \le (n-j)/21≤p≤(n−j)/2因为至少需要两个周期才能压缩。从jjj开始检查字符串是否以S[j…jp−1]S[j \ldots jp-1]S[j…jp−1]为周期连续重复。我们可以用一个循环记录当前能够匹配到的最远位置maxLen即满足S[jt]S[j(t mod p)]S[jt] S[j (t \bmod p)]S[jt]S[j(tmodp)]的最大ttt。对于每个可能的重复次数kkk2≤k2 \le k2≤k且p⋅k≤maxLenp \cdot k \le \textit{maxLen}p⋅k≤maxLen子串S[j…jp⋅k−1]S[j \ldots j p \cdot k - 1]S[j…jp⋅k−1]可以压缩为(X)k(X)k(X)k其中XS[j…jp−1]X S[j \ldots jp-1]XS[j…jp−1]压缩后的长度为2pdigits(k)2 p \text{digits}(k)2pdigits(k)。更新cost[j][jp⋅k]min⁡(cost[j][jp⋅k],2pdigits(k))\textit{cost}[j][j p \cdot k] \min(\textit{cost}[j][j p \cdot k], 2 p \text{digits}(k))cost[j][jp⋅k]min(cost[j][jp⋅k],2pdigits(k))。注意这里我们仅使用一级压缩即压缩后的块不能再包含压缩因此我们不需要考虑嵌套。每个压缩块独立其内部是原字符串的子串不涉及其他压缩。这正是预处理时直接计算原始子串重复次数的原因。动态规划转移定义dp[i]\textit{dp}[i]dp[i]为前缀S[0…i−1]S[0 \ldots i-1]S[0…i−1]压缩后的最小长度。初始化dp[0]0\textit{dp}[0] 0dp[0]0。对于iii从111到nnn先令dp[i]dp[i−1]1\textit{dp}[i] \textit{dp}[i-1] 1dp[i]dp[i−1]1第i−1i-1i−1个字符单独保留。然后对于所有jij iji如果cost[j][i]≠∞\textit{cost}[j][i] \ne \inftycost[j][i]∞则尝试转移dp[i]min⁡(dp[i],dp[j]cost[j][i])\textit{dp}[i] \min(\textit{dp}[i], \textit{dp}[j] \textit{cost}[j][i])dp[i]min(dp[i],dp[j]cost[j][i])。最终答案即为dp[n]\textit{dp}[n]dp[n]。正确性说明预处理枚举了所有可能的周期和重复次数因此任何可压缩的子串都会被考虑到并记录其最优压缩长度。DP\texttt{DP}DP的过程考虑了所有可能的分割方式包括不压缩任何部分的平凡分割因此能够找到全局最优解。由于压缩不能嵌套我们的分割是平坦的即每个块要么是单个字符要么是(X)k块之间无嵌套这完全符合题意。复杂度分析设n∣S∣n |S|n∣S∣n≤100n \le 100n≤100。预处理阶段枚举jjjO(n)O(n)O(n)枚举pppO(n)O(n)O(n)对于每个j,pj, pj,p计算maxLen最多扫描O(n)O(n)O(n)长度再枚举kkk总复杂度为O(n3)O(n^3)O(n3)即10610^6106数量级完全可以接受。DP\texttt{DP}DP阶段O(n2)O(n^2)O(n2)。空间复杂度O(n2)O(n^2)O(n2)存储cost\textit{cost}cost。由于T≤100T \le 100T≤100总运算量约为100×106100 \times 10^6100×106在 C 中完全可行。代码实现// Lets call SPaDe a SPaDe// UVa ID: 12451// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 计算整数 x 的十进制位数 (x 2)intdigitCount(intx){intcnt0;while(x0){cnt;x/10;}returncnt;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){string S;cinS;intn(int)S.size();constintINF1e9;// cost[j][i] 表示子串 S[j..i-1] 整体压缩后的最短长度若不可压缩则为 INFvectorvectorintcost(n,vectorint(n1,INF));// 枚举起点 j 和周期 p计算所有可压缩的块for(intj0;jn;j){// p 至少为 1且需要至少两个周期所以 p (n-j)/2for(intp1;p(n-j)/2;p){// 计算从 j 开始能连续匹配模式 S[j..jp-1] 的最大长度 maxLenintmaxLen0;while(jmaxLennS[jmaxLen]S[jmaxLen%p]){maxLen;}// 枚举重复次数 k (k 2)for(intk2;p*kmaxLen;k){intlenp*k;intcurCost2pdigitCount(k);// 括号2个 子串长度 数字位数if(curCostcost[j][jlen]){cost[j][jlen]curCost;}}}}// 动态规划dp[i] 表示前缀 S[0..i-1] 的最短压缩长度vectorintdp(n1,INF);dp[0]0;for(inti1;in;i){// 不压缩当前字符直接拼接dp[i]dp[i-1]1;// 尝试以 i 结尾的压缩块起点 jfor(intj0;ji;j){if(cost[j][i]!INF){dp[i]min(dp[i],dp[j]cost[j][i]);}}}coutdp[n]\n;}return0;}总结本题是一道典型的区间DP\texttt{DP}DP与字符串周期检测问题。由于数据范围很小∣S∣≤100|S| \le 100∣S∣≤100直接枚举所有子串及其周期并计算压缩代价即可无需复杂数据结构。关键点与技巧周期检测利用取模运算验证字符串是否为某模式的重复时间复杂度O(n3)O(n^3)O(n3)在本题限制下可行。压缩长度计算注意数字kkk的位数以及括号占用的两个字符。动态规划将原问题分解为前缀的最优解通过枚举最后一个块完成转移这种分割方式天然避免了嵌套问题。细节处理初始化cost\textit{cost}cost为无穷大表示不可压缩dp[0]0\textit{dp}[0] 0dp[0]0保证前缀为空时的正确性。本题虽然简单但综合运用了周期枚举、动态规划和字符串处理是练习基础DP\texttt{DP}DP和贪心思维的好题。