Problem 3487 --整理图书

3487: 整理图书

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $4$ 正确数量 $3$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划
小明是图书鹳狸猿,他有很多很多的书堆在了一起摆在了架子上,每摞书是横着放的,而且每摞书是订好的
是一个整体,不可分开,(可以想象架子是一条直线),但是这些书高度却参差不齐,小明有强迫症,看不得不整齐
所以他想让这些书的高度形成一个非降序列他才舒心,可是这些书是有序的,所以他只能把其中的一摞书和他相邻的书装订在一起
形成一摞新的书,那么他最少的装订次数是多少呢
多组测试数据,处理到文件结束
每组数据开始有一个n(1<=n<=1000)表示有n摞书
接下来一行是这n摞书的高度a[i],(1<=a<=10^5)(虽然这个高度有点扯淡)
首先输出Case num : 表示第几组数据
接下来对于每组数据输出最少的装订次数
5
8 2 7 3 1
1
100
Case 1: 3
Case 2: 0
第一组样例:将后4本书装订在一起,共装订3次,组成8 13
第二组样例:只有一本书,无需装订

推荐代码 查看3487 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$2 $ms] 快乐的小2B 762211 2021-08-25 23:20:58
内存最少[$0 $KB] aoj_judger 615440 2020-10-08 17:33:17
第一AC aoj_judger 615440 2020-10-08 17:33:17
第一挑战 aoj_judger 615440 2020-10-08 17:33:17

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛