Problem 2528 --核发电站

2528: 核发电站

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $41$ 正确数量 $5$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划
有N个位于一条直线上的城市,由于城市供电系统不足,城市设计师
想选择一些城市建设核发电站一供发电。现在有M种规模核发电站以
供选择,已知第K种规模核发电站的辐射半径是K。例如在第I座城市
建立第K种规模核发电站,一旦该城市的核发电站发生爆炸,那么[IK,I+K]区间内的城市都会受到辐射。假设此刻存在一些核发电站处于
辐射范围内,那么这些核发电站也会接连发生爆炸。
核发电站的安全需要技术人员来保障,而城市设计师的任务是选择合
适的建设方案,在设计上杜绝连锁爆炸的发生。现在城市设计师想咨
询你一共有多少个符合要求的设计方案。

第一行输入 整数 T,代表有 T组数据。
接下来每行代表一个数据,分别是 N(0<N<10000) ,M(0<M<100)
对于每组数据,输出一行格式为 ‘Case t: x’ ,其中 t为数据组号,
x为方案数。由于过大,请输出对 1000000007 取余的结果。
2
3 2
4 2
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 请登录