当前位置: 首页 > news >正文

26 UVA1630 串折叠 Folding 题解

Folding

题面

折叠由大写字母组成的长度为 \(n\)\(1\leqslant n\leqslant100\))的一个字符串,使得其成为一个尽量短的字符串,例如 AAAAAA 变成 6(A)

这个折叠是可以嵌套的,例如 NEEEEERYESYESYESNEEEEERYESYESYES 会变成 2(N5(E)R3(YES))

多解时可以输出任意解。

题解

首先,数据范围很小,可能是区间dp,又因为这玩意贪心肯定不对,而且我看题解了,就是区间dp

考虑怎么区间dp,设 \(f(l,r)\) 表示 \([l,r]\) 区间最短字符串长度,有两种转移方式

  • 不折叠,枚举分界点,\(f(l,r) = f(l,k) + f(k + 1, r)\)
  • 折叠,枚举循环子串长度 \(len\)\(f(l,r) = 2 + calc((r - l + 1) / len) + len\)

calc表示计算 x 的位数,2表示两个括号,len表示枚举的循环子串的长度

时间复杂度 \(O(n^4)\)

code

http://www.hskmm.com/?act=detail&tid=25025

相关文章:

  • 13 ACwing 283 Polygon 题解
  • 12 ACwing 282 石子合并 题解
  • 11 ACwing 281 Coins 题解
  • 某中心科学家荣获多项计算机技术大奖
  • FFT
  • 4 ACwing 274 Mobile Service 题解
  • 3 ACwing 273 Making the Grade 题解
  • 1 ACwing 271 Mr
  • 2 ACwing 272 LCIS 最长公共上升子序列 题解
  • 用 Haxe 实现英文数字验证码识别
  • 出题四
  • 7 2025 07 15 模拟赛题解
  • 使用 OCaml 实现验证码识别
  • 私有云大数据部署:从开发到生产(Docker、K8s、HDFS/Flink on K8s) - 详解
  • 差分约束模板
  • 17 LCA模拟赛1T2 剧院始于演员 题解
  • 3 2025 04 23 模拟赛总结
  • 14 收心赛3 T1 最长不降子序列 题解
  • 16 LCA模拟赛1T1 密码 题解
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(一)
  • 阿里开源规则引擎QLExpress
  • QOJ7411 Bitwise Xor
  • 完整教程:SOC-ESP32S3部分:25-HTTP请求
  • 为什么要采用“接口 - 抽象类 - 实现类”这种三层结构? - 浪矢
  • 对外提供 AI 服务的风险:合规视角与 AI 安全围栏落地指南
  • VScode C/C++ 汉化 竞赛版 只需下载扩展 (超简单)
  • 网络安全工具与社区讨论月报
  • 机器人运动未来与人机交互研究
  • 欧拉路径 欧拉图 小记
  • OI 笑传 #16