首页 > 试题广场 >

CCNumber

[编程题]CCNumber

热度指数：864 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

CC最近对一种整数比较感兴趣，我们暂且把这种整数称为C Number, C Number是指一个整数 {C0, C1 … Cn-1} (C0 > 0 , n >= 3)，存在一个Cm（0<m<n-1）满足以下条件:
    Ci-1 < Ci (0<i<=m), Ci代表这个整数中的第i位数字
    Ci>Ci+1(m<=i<n-1)
    如果一个整数里面有相邻的2个C Number的话，我们称这个整数为CC Number（2个C Number不可以有公用的数字Ci，并且2个C Number要紧紧相邻）。
    请在[A,B]区间内找出找出score最大的CCNumber 并输出这个score.(score：CC Number中所有数字的和)

输入描述:

第一行为数字N(N<=1000),后面有N行测试用例
每行用例有2个数字 A,B（0<=A<=B<2^64）,需要[A,B]区间内找出题干中描述的最大score。

输出描述:

对于第N行的测试用例，输出“Case N: S”, S为最大的score，如果区间内没有CC Number的话 S为0。

示例1

输入

4
12121 12121
120010 120010
121121 121121
1211121 1211121

输出

Case 1: 0
Case 2: 0
Case 3: 8
Case 4: 0

算法知识视频讲解

牛客题解官

发表于 2020-06-05 17:38:17

精华题解题解难度：较难知识点：动态规划，数学逻辑题目分析 CNumber就是一个山形状的整数，例如121，123421，18910这些数，都是先变大后变小，相邻数字间只能有大于或小于的关系，不能等于，CNumber最少3位数 CCNumber就是两个紧邻的山构成的整数，意思就是这个数可以分为两个子展开全文