Problem 2528 --核发电站

2528: 核发电站

上一题 正确率: $12.20\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $41$ 正确数量 $5$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划

Description

有N个位于一条直线上的城市，由于城市供电系统不足，城市设计师
想选择一些城市建设核发电站一供发电。现在有M种规模核发电站以
供选择，已知第K种规模核发电站的辐射半径是K。例如在第I座城市
建立第K种规模核发电站，一旦该城市的核发电站发生爆炸，那么[IK,I+K]区间内的城市都会受到辐射。假设此刻存在一些核发电站处于
辐射范围内，那么这些核发电站也会接连发生爆炸。
核发电站的安全需要技术人员来保障，而城市设计师的任务是选择合
适的建设方案，在设计上杜绝连锁爆炸的发生。现在城市设计师想咨
询你一共有多少个符合要求的设计方案。
注

Input

第一行输入 整数 T，代表有 T组数据。
接下来每行代表一个数据，分别是 N(0<N<10000) ，M(0<M<100)

Output

对于每组数据，输出一行格式为 ‘Case t: x’ ，其中 t为数据组号，
x为方案数。由于过大，请输出对 1000000007 取余的结果。

Sample Input复制

2
3 2
4 2

Sample Output复制

Case 1: 8
Case 2: 15

提示

样例解释：对于第一组样例有以下八种方案数：

0 0 0；1 0 0；0 1 0；0 0 1；1 0 1；2 0 0；0 2 0；0 0 2；

0代表不建核发电站，数字1,2代表建造第1,2种规模核发电站。

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

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$94 $ms] 罗春阳 854303 2022-05-11 17:23:06
内存最少[$6056 $KB] 淡意的温柔 605985 2020-07-07 14:48:25
第一AC AOJ大管家 244633 2018-05-13 19:08:38
第一挑战 AOJ大管家 244631 2018-05-13 19:07:59

赛题来源/所属竞赛 2017年“华信智原杯”安徽省大学生程序设计大赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1351 大学生程序设计大赛模拟赛4 2019-05-16 09:00:00 请登录