Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5106 --巧背圆周率
5106: 巧背圆周率
警告!
题目
状态
题解(1)
题目描述
想要背诵一段很长的数字,比如圆周率,可以将这些数字分割成一个个**片段**,根据每个**片段**的规律做不同的记忆训练。不妨假定每个**片段**最少 $3$ 个数,最多 $6$ 个数,各种**片段**的**记忆难度**定义如下: + 若所有数字相同,如 `666`,`88888` 等,则**记忆难度**为 $1$; + 公差为 $1$ 或者 $-1$ 的等差数列,如 `3456`,`43210` 等,**记忆难度**为 $2$; + 两个数字交替出现,如 `313`,`68686` 等,**记忆难度**为 $4$; + 其他等差数列,如 `7531`,`369` 等,**记忆难度**为 $5$,但注意 `36912` 不算等差数列,因为我们只考虑一位数字; + 不属于上述任何一条规律的,比如 `2794` 等,**记忆难度**为 $10$。 现在给定一个由数字构成的字符串 $s$,请找出一个分割**片段**的方法,使得所有**片段**的**记忆难度**之和最小。
输入
一个由数字构成的字符串 $s$。
输出
单个整数:表示**记忆难度**之和的最小值。
样例输入输出
输入#1
复制
314159265358979323846
输出#1
复制
34
输入#2
复制
271828182845904523536
输出#2
复制
40
输入#3
复制
12122222
输出#3
复制
5
提示
设 $s$ 的长度为 $n$,则 + 对 $30\%$ 的数据 $3\leq n\leq 20$; + 对 $60\%$ 的数据 $3\leq n\leq 10000$; + 对 $100\%$ 的数据 $3\leq n\leq 100000$。 样例1说明:分成(314159)(265358)(979)(323846),总难度为10+10+4+10=34 样例2说明:分成(271828)(182845)(904523)(536),总难度为40 样例3说明:分成(1212)(2222),总难度4+1=5
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及+/提高-
标签
动态规划
点击显示
if ($pr_flag) { ?>
递交数
1
已通过
1
} ;?>
通过率
100%
时间限制
1 秒
内存限制
256 MB
来源
YACS2020年3月月赛乙组
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和