2023牛客暑期多校-J-Qu‘est-ce Que C‘est?(DP)

news/2024/3/29 5:19:35/文章来源:https://blog.csdn.net/qq_63108111/article/details/131993444

题意:

给定长度为n的数列{a}_{i=1}^{n},要求每个数都在[-m,m]的范围,且任意长度大于等于2的区间和都大于等于0,问方案数。1\leq n,m\leq 5\times 10_{}^{3}

思路:

首先要看出是dp题,dp[i][x]用来表示遍历到第i位且后缀和最小为x的可行方案数(此时的后缀可以只有最后一位)。很显然j的值在区间[-m,m]。下面考虑dp如何转换:

        1.对于x\epsilon [0,m]。 先讨论dp[i][0]dp[i][0]可由dp[i-1][j],j< 0加一位值为 -j 转换而来;也可由dp[i-1][j],j>=0加一位值为0 转换而来。就有dp[i][0]=\sum_{j=-m}^{m} dp[i-1][j]。再讨论dp[i][1],可由dp[i-1][j],j<0,1-j\leq m,加一位值为 1-j 转换而来;也可由 dp[i-1][j],j>=0加一位值为1转换而来。就有dp[i][1]=\sum_{j=1-m}^{m} dp[i-1][j]。依次讨论可以得出dp[i][x]可以由dp[i-1][j],j< 0,x-j<=m,末位加值为x-j转换而来;也可由dp[i-1][j],j>=0,末位加x转换而来。综上所诉:dp[i][x]=\sum_{j=x-m}^{m} dp[i-1][j]

        2.对于x\epsilon [-m,0)。可以去验证,只有dp[i-1][j],j>=-x,末位加值为x才能转换成dp[i][x]。所以dp[i][x]=\sum_{j=-x}^{m}dp[i-1][j]

为了方便计算我们把[-m,m]这个区间平移映射到[0,2m]区间上。按照上述思想去找新的dp转换式就有:

dp[i][x]=\sum_{j=x-m}^{2m}dp[i-1][j],x\varepsilon [m,2m]

dp[i][x]=\sum_{j=2m-x}^{2m}dp[i-1][j],x\epsilon [0,m)

由于都是求和到2m,所以可以考虑后缀和优化。

代码:

//#define _CRT_SECURE_NO_WARNINGS 
//#include<iostream>
//#include<algorithm>
//#include<cstdio>
//#include<map>
//#include<string.h>
//#include<string>
//#include<vector>
//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;
const int N = 5005;
ll dp[N][N*2];//dp[i][j]表示遍历到i位,后缀和最小为j且合法的数量。(这里后缀和包含了只含有最后一位的情况)
ll sum[N * 2];//后缀数组
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;ll ans = 0;//初始化for (int i = 0; i <= m*2; i++){dp[1][i] = 1;}for (int i = 2; i <= n; i++){//处理后缀和for (int j = m * 2; j >= 0; j--)sum[j] = (sum[j + 1] + dp[i - 1][j]) % mod;//[0,m)的情况for (int j = 0; j < m; j++){dp[i][j] = sum[2 * m - j];}//[m,2m]的情况for (int j = m; j <= 2 * m; j++){dp[i][j] = sum[j - m];}}//统计for (int i = 0; i <= m * 2; i++){ans = (ans + dp[n][i]) % mod;}cout << ans << endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_337136.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java 版 spring cloud +spring boot 工程系统管理 工程项目管理系统源码 工程项目各模块及其功能点清单

工程项目各模块及其功能点清单 一、系统管理 1、数据字典&#xff1a;实现对数据字典标签的增删改查操作 2、编码管理&#xff1a;实现对系统编码的增删改查操作 3、用户管理&#xff1a;管理和查看用户角色 4、菜单管理&#xff1a;实现对系统菜单的增删改查操…

linux下nginx的安装和使用

文章目录 &#x1f4d2;安装nginx正常使用nginx包安装1️⃣上传到对应目录2️⃣解压nginx3️⃣检查是否启动成功 使用docker安装nginx &#x1f4d2;使用nginx1️⃣简单的反向代理2️⃣介绍location配置中root和alias的区别 &#x1f4d2;安装nginx 正常使用nginx包安装 官网…

BLE基础理论/Android BLE开发示例

参考&#xff1a;https://blog.csdn.net/qq_36075612/article/details/127739150?spm1001.2014.3001.5502 参考&#xff1a; https://blog.csdn.net/qq_36075612/article/details/122772966?spm1001.2014.3001.5502 目录 蓝牙的分类传统蓝牙低功耗蓝牙 蓝牙专业词汇&#xff…

SpringAOP的相关概念

文章目录 一.什么是AOP二.AOP的组成部分三.SpringAOP的实现3.1 增加SpringAOP依赖3.2 创建切面3.2 创建切点3.3 创建通知3.4 创建连接点 四.SpringAOP的实现原理4.1 JDK动态代理4.2 CGLIB 动态代理总结 一.什么是AOP AOP&#xff0c;全称为Aspect-Oriented Programming&#x…

解决 tensorflow 出现的 ImportError: Could not find the DLL(s) ‘msvcp140_1.dll‘. 问题

在安装完tensorflow库后出现 问题详述&#xff1a; ImportError: Could not find the DLL(s) msvcp140_1.dll. TensorFlow requires that these DLLs be installed in a directory that is named in your %PATH% environment variable. You may install these DLLs by downlo…

新零售行业如何做会员管理和会员营销

蚓链数字化营销系统全渠道会员管理解决方案&#xff0c;线上线下统一管理&#xff0c;打造私域流量&#xff0c;微信、门店会员全渠道管理&#xff0c;打通私域流量池&#xff0c;实现裂变营销&#xff1a; 开启新零售之路&#xff0c;必然要摒弃原有的管理模式&#xff0c;大…

郑州多域名https证书

多域名https证书是https证书中比较特殊的一款&#xff0c;它保护的域名记录是众多https证书中最灵活的。不管是DV基础型的多域名https证书还是OV企业型和EV增强型的多域名https证书既可以保护多个主域名或者子域名&#xff0c;还可以主域名子域名随意组合&#xff0c;只要申请者…

【动态规划part11】| 123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV

目录 &#x1f388;LeetCode123.买卖股票的最佳时机III &#x1f388;LeetCode188.买卖股票的最佳时机IV &#x1f388;LeetCode123.买卖股票的最佳时机III 链接&#xff1a;123.买卖股票的最佳时机III 给定一个数组&#xff0c;它的第 i 个元素是一支给定的股票在第 i…

无涯教程-jQuery - Pulsate方法函数

Pulsate 效果可以与effect()方法一起使用。这会使元素的不透明性产生多次脉冲。 Pulsate - 语法 selector.effect( "pulsate", {arguments}, speed ); 这是所有参数的描述- times - 脉动的时间。默认值为3。model - 效果的模式。可以是"显示(show)"&a…

基于Java+SpringBoot+vue前后端分离技术交流和分享平台设计实现

博主介绍&#xff1a;✌全网粉丝30W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专…

Moke 一百万条 Mysql 的数据

文章目录 前言创建数据库创建表结构生成数据 前言 想研究一下&#xff0c;数据量大的情况下&#xff0c;如何优化前端分页&#xff0c;所以需要 Moke 一些数据 创建数据库 在 Mysql的基础上&#xff0c;可以写个语句执行 CREATE DATABASE test_oneMillion; USE test_oneMi…

JAVA SE -- 第十一天

&#xff08;全部来自“韩顺平教育”&#xff09; 异常-Exception 一、异常介绍 1、基本介绍 Java语言中&#xff0c;将程序执行中发生的不正常情况为“异常”&#xff08;开发过程中的语法错误和逻辑错误不是异常&#xff09; 2、执行过程中发生的异常事件可分为两大类 …

Reinforcement Learning with Code 【Chapter 9. Policy Gradient Methods】

Reinforcement Learning with Code This note records how the author begin to learn RL. Both theoretical understanding and code practice are presented. Many material are referenced such as ZhaoShiyu’s Mathematical Foundation of Reinforcement Learning, . 文章…

opencv+ffmpeg环境(ubuntu)搭建全面详解

一.先讲讲opencv和ffmpeg之间的关系 1.1它们之间的联系 我们知道opencv主要是用来做图像处理的&#xff0c;但也包含视频解码的功能&#xff0c;而在视频解码部分的功能opencv是使用了ffmpeg。所以它们都是可以处理图像和视频的编解码&#xff0c;我个人感觉两个的侧重点不一…

SpringBoot项目部署(前后端分离、Linux部署项目)

一、架构 部署环境说明&#xff1a; 192.168.122.100(服务器A)&#xff1a; Nginx&#xff1a;部署前端项目、配置反向代理 Mysql&#xff1a;主从复制结构中的主库 192.168.122.131 (服务器B)&#xff1a; jdk: 运行Java项目 git:版本控制工具 (从gitee中拉取源码) maven:…

数据结构:快速的Redis有哪些慢操作?

redis 为什么要这莫快&#xff1f;一个就是他是基于内存的&#xff0c;另外一个就是他是他的数据结构 说到这儿&#xff0c;你肯定会说&#xff1a;“这个我知道&#xff0c;不就是 String&#xff08;字符串&#xff09;、List&#xff08;列表&#xff09;、 Hash&#xff08…

【SpringCloud Alibaba】(五)服务雪崩与容错方案

在前面的文章中&#xff0c;我们实现了用户微服务、商品微服务和订单微服务之间的远程调用&#xff0c;并且实现了服务调用的负载均衡。 但是&#xff0c;现在系统中存在着一个很明显的问题&#xff1a;那就是如果系统的并发量上来后&#xff0c;系统并没有容错的能力&#xf…

Java | 继承、多态、抽象类与接口

目录 一、类的继承 二、Object类 2.1 getClass()方法 2.2 toString()方法 2.3 equals()方法 三 、对象类型的转换 3.1 向上转换 3.2 向下转型 四、使用instanceof关键字判断对象类型 五、方法的重载 六、final关键字 6.1 final变量 6.2 final方法 6.3 final类 七…

LeetCode 1857. Largest Color Value in a Directed Graph【拓扑排序,动态规划】困难

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…

【UE5】快速认识入门

目录 &#x1f31f;1. 快速安装&#x1f31f;2. 简单快捷键操作&#x1f31f;3. 切换默认的打开场景&#x1f31f;4. 虚幻引擎术语 &#x1f31f;1. 快速安装 进入Unreal Engine 5官网进行下载即可&#xff1a;UE5 &#x1f4dd;官方帮助文档 打开后在启动器里创建5.2.1引擎…