核发电站 (dp前缀优化)
2024-09-03 06:06:13
大意: $n$个城市, $m$种核电站, 第$i$种假设要建在第$x$个城市, 必须满足$[x-i,x+i]$范围内无其他核电站, 求建核电站的方案数.
简单$dp$题, 设$dp[i][j]$为位置$i$建第$j$种核电站的方案数.
枚举上一个核电站的位置来转移, 有:
$dp[i][1]=1+dp[i-2][1]+\sum\limits_{k=1}^2 dp[i-3][k]+\sum\limits_{k=1}^3dp[i-4][k]+...$
$dp[i][j]=dp[i][j-1]-\sum\limits_{k=1}^{j-1}dp[i-j][k],\space j>1$.
前缀优化一下即可$O(nm)$.
#include <iostream>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
using namespace std;
const int P = 1e9+7;
int dp[10010][110], s[10010]; int main() {
int t;
scanf("%d", &t);
REP(cas,1,t) {
int n, m;
scanf("%d%d", &n, &m);
REP(i,1,n) {
int now = 1;
dp[i][1] = 1;
PER(j,1,i-2) {
if (now==m) {
(dp[i][1] += s[j]) %= P;
break;
}
(dp[i][1] += dp[j][now++]) %= P;
}
REP(j,2,m) dp[i][j] = (dp[i][j-1]-(i-j>0?dp[i-j][j-1]:0))%P;
REP(j,2,m) (dp[i][j] += dp[i][j-1]) %= P;
s[i] = (s[i-1]+dp[i][m])%P;
}
int ans = (s[n]+1)%P;
if (ans<0) ans += P;
printf("Case %d: %d\n", cas, ans);
}
}
最新文章
- [LeetCode] Sudoku Solver 求解数独
- return Acad::ErrorStatus::eOk引发error C2220: warning treated as error - no &#39;object&#39; file generated
- 开源服务专题之--------mysql的编译安装
- JVM参数调优
- Maven下载安装
- 配置新系统(Win7 x64)
- Intellij编译时报“java: System Java Compiler was not found in classpath”
- VIJOS P1647 不差钱 SBT
- MD5碰撞后时代,MD5还有存在的意义吗?
- 使用IO流实现音频的剪切和拼接
- 【NOIP2015提高组】 Day1 T3 斗地主
- 分布式监控系统--zabbix
- python模块:时间处理模块
- (十分钟视频教程)nodejs基础实战教程3:react服务端渲染入门篇
- python to shell vimdiff
- sprite kit -- 从入门到淡定
- orcal - 增删改
- vue 构建项目遇到的问题
- Linux的学习 --corntab
- SpringBoot添加对jsp的支持
热门文章
- Linux设备驱动程序 之 中断下半部
- mysql—并发控制及事务
- 【Linux】安装 PostgreSQL
- 阶段5 3.微服务项目【学成在线】_day05 消息中间件RabbitMQ_15.RabbitMQ研究-与springboot整合-声明交换机和队列
- Qt编写安防视频监控系统11-动态换肤
- Qt编写安防视频监控系统7-全屏切换
- OnPreInit,OnInit ,OnInitComplete ,OnPreLoad ,Page_Load等执行顺序
- mysql表如何使用redis保存?
- bash小结
- GCE 部署 ELK 7.1可视化分析 nginx