【AtCoder Beginner Contest 253】E - Distance Sequence

简介: 笔记

题意


5.png


思路


6.png7.png

代码


  • 前缀和 + 动态规划
int n, m, k;
int f[M], s[M];
void solve() {
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) f[i] = 1; // i == 1;
  for (int i = 2; i <= n; i++) { // i > 1
    s[0] = 0;
    for (int j = 1; j <= m; j++)
      s[j] = (s[j - 1] + f[j]) % mod;
    int sum = s[m];
    for (int j = 1; j <= m; j++) {
      int l = max(1ll, j - k + 1);
      int r = min(m, j + k - 1);
      if(k > 0) f[j] = (sum - s[r] + s[l - 1] + mod) % mod;
      else f[j] = sum % mod;
    }
  }
  int res = 0;
  for (int i = 1; i <= m; i++) res = (res + f[i]) % mod;
  cout << res << endl;
}
相关文章
|
5月前
|
移动开发 JavaScript Java
开发体育赛事平台:专家预测系统功能模块解析与技术实现全方案
专家预测系统是体育直播平台的核心商业化功能之一,该系统支持用户申请成为专家,经审核后可发布赛事预测内容,其他用户需付费查看,平台抽取分成。系统包含专家认证、内容发布、付费阅读、数据统计等功能模块,并通过MySQL数据库管理用户、文章及购买记录等信息。技术实现涵盖PHP后端(ThinkPHP框架)、Java Android客户端与Vue.js H5移动端,提供完整的预测发布、付费机制与胜率收益统计解决方案。
|
11月前
|
安全 Java 程序员
深入Java集合框架:解密List的Fail-Fast与Fail-Safe机制
本文介绍了 Java 中 List 的遍历和删除操作,重点讨论了快速失败(fail-fast)和安全失败(fail-safe)机制。通过普通 for 循环、迭代器和 foreach 循环的对比,详细解释了各种方法的优缺点及适用场景,特别是在多线程环境下的表现。最后推荐了适合高并发场景的 fail-safe 容器,如 CopyOnWriteArrayList 和 ConcurrentHashMap。
223 5
|
存储 开发者 微服务
一键托管,阿里云全链路追踪服务正式商用:成本仅自建1/5或更少
基于 Opentracing 标准,可实现 Jaeger, Zipkin 和 Skywalking等开源方案在阿里云上的托管。
26963 90
|
存储 缓存 算法
Python缓存神器cachetools:提高程序性能的利器,一文详解其缓存算法
Python缓存神器cachetools:提高程序性能的利器,一文详解其缓存算法
Python缓存神器cachetools:提高程序性能的利器,一文详解其缓存算法
|
设计模式 Java
Java线程(上)
Java线程(上)
82 0
|
IDE 编译器 开发工具
【NXP】LPC55S69-RT-Thread Micropython移植日志
【NXP】LPC55S69-RT-Thread Micropython移植日志
298 0
|
存储 监控 前端开发
微服务-监控
这篇其实本来也打算放在《常识》系列中的,介绍一下分布式日志追踪系统,这在互联网界理论,技术,产品已经很成熟,国内外各大厂都有自己成熟的产品。是个不错的互联网门外汉科普知识点 微服务,已经火了多年,也已经落地实施。对服务的监控需求顺理成章。监控系统的本质其实也就是分布式日志追踪系统。就归类到《微服务》系列中吧 本篇大体内容
407 0
微服务-监控
|
传感器
Google Earth Engine ——GIMMS NDVI是由NOAA的几个AVHRR传感器为全球1/12度的纬度/龙格生成的数据集
Google Earth Engine ——GIMMS NDVI是由NOAA的几个AVHRR传感器为全球1/12度的纬度/龙格生成的数据集
297 0
Google Earth Engine ——GIMMS NDVI是由NOAA的几个AVHRR传感器为全球1/12度的纬度/龙格生成的数据集
|
人工智能 自然语言处理 算法
谷歌搜索中的人工智能
本文最初发布于 HData Systems 博客,经 InfoQ 翻译。
377 0
|
监控 iOS开发
iOS - Runtime Method Swizzling(下)
Runtime合集 iOS - Runtime基础

热门文章

最新文章