当前位置: 首页 > news >正文

洛谷 CF295D Greg and Caves

题目来源于:洛谷

题目本质:动态规划dp,枚举

解题思路:将整个洞分成两半,一半递增,一半递减。我们分别 DP 求值,最后合并。状态转移方程为:dpi,j​=k=2∑j​(j−k+1)dpi−1,k​+1。枚举极大最长行区间来代替最长行。

代码如下:

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
const int N=2000,M=N;
int n,m;
int dp[N+1][M+1];
int Sum[N+1][M+1],Sumk[N+1][M+1];
int sum[N+2];
int main(){cin>>n>>m;for(int i=2;i<=m;i++){dp[1][i]=1;Sum[1][i]=(Sum[1][i-1]+dp[1][i])%mod,Sumk[1][i]=(Sumk[1][i-1]-1ll*i*dp[1][i])%mod;}for(int i=2;i<=n;i++){for(int j=2;j<=m;j++){dp[i][j]=(1ll*(j+1)*Sum[i-1][j]+Sumk[i-1][j]+1)%mod;Sum[i][j]=(Sum[i][j-1]+dp[i][j])%mod;Sumk[i][j]=(Sumk[i][j-1]-1ll*j*dp[i][j])%mod;}}int ans=0;for(int k=2;k<=m;k++){for(int j=n;j;j--){sum[j]=(1ll*sum[j+1]+dp[n-j+1][k]-dp[n-j][k])%mod;}for(int i=1;i<=n;i++){(ans+=1ll*(m-k+1)*(dp[i][k]-dp[i-1][k])%mod*sum[i]%mod)%=mod;}}cout<<(ans+mod)%mod;return 0;
}

相关文章:

洛谷 CF295D Greg and Caves

题目来源于&#xff1a;洛谷 题目本质&#xff1a;动态规划dp&#xff0c;枚举 解题思路&#xff1a;将整个洞分成两半&#xff0c;一半递增&#xff0c;一半递减。我们分别 DP 求值&#xff0c;最后合并。状态转移方程为&#xff1a;dpi,j​k2∑j​(j−k1)dpi−1,k​1。枚举极…...

【图像处理】在图像处理算法开发中,有哪些常见的主观评价指标和客观评价指标?

主观评价指标 在图像处理算法开发中&#xff0c;主观评价指标依赖于观察者的个人感受和判断&#xff0c;通常用于评估图像的视觉质量。以下是一些常见的主观评价指标&#xff1a; 平均意见分数 (Mean Opinion Score, MOS)&#xff1a;通过收集多个评价者的评分并计算平均值来评…...

从零开始学cv-6:图像的灰度变换

文章目录 一&#xff0c;简介&#xff1a;二、图像的线性变换三、分段线性变换四&#xff0c;非线性变换4.1 对数变换4.2 Gamma变换 五&#xff0c;效果: 一&#xff0c;简介&#xff1a; 图像灰度变换涉及对图像中每个像素的灰度值执行数学运算&#xff0c;进而调整图像的视觉…...

使用Apache POI和POI-OOXML实现word模板文档自动填充功能

最近接到一个新的需求&#xff0c;用户创建好模板文件保存到模板库&#xff0c;然后使用在线文档编辑器打开模板时&#xff0c;将系统数据填充到模板文件并生成新的word文件&#xff0c;然后在线编辑&#xff0c;研究使用Apache POI和POI-OOXML实现了这个功能。 Maven依赖 <…...

【HarmonyOS NEXT星河版开发学习】综合测试案例-各平台评论部分

目录 前言 功能展示 整体页面布局 最新和最热 写评论 点赞功能 界面构建 初始数据的准备 列表项部分的渲染 底部区域 index部分 知识点概述 List组件 List组件简介 ListItem组件详解 ListItemGroup组件介绍 ForEach循环渲染 列表分割线设置 列表排列方向设…...

垂直行业数字化表现抢眼 亚信科技全年利润展望乐观

大数据产业创新服务媒体 ——聚焦数据 改变商业 2024年8月14日&#xff0c;亚信科技控股有限公司&#xff08;股票代码&#xff1a;01675.HK&#xff09;公布了公司截至2024年6月30日的中期业绩。 财报数据显示&#xff0c;2024年上半年&#xff0c;亚信科技的营业收入为人民币…...

EmguCV学习笔记 VB.Net 4.1 颜色变换

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 教程VB.net版本请访问&#xff1a;EmguCV学习笔记 VB.Net 目录-CSDN博客 教程C#版本请访问&#xff1a;EmguCV学习笔记 C# 目录-CSD…...

【MySQL进阶之路】表结构的操作

目录 创建表 查看表 查看数据库有哪些表 查看表结构 查看表的详细信息 修改表 表的重命名 添加一列 修改某一列的属性 删除某一列 对列进行重命名 删除表 个人主页&#xff1a;东洛的克莱斯韦克-CSDN博客 【MySQL进阶之路】MySQL基础——从零认识MySQL-CSDN博客 创…...

3分钟搞定PDF转PPT!你一定要知道的3款转换神器!

在数字办公成为主流的当下&#xff0c;我们每天会收到各类基于数字化方式存储的办公文档&#xff0c;如PDF、PPT、Word、Excel文档等。 日常处理这些文档时&#xff0c;经常需要在不同格式的文档之间进行切换和转换&#xff0c;其中将PDF转换为PPT就是一个非常高频的需求&…...

【EasyExcel】导出excel-设置动态表头并导出数据

需求背景&#xff1a; 导出excel的设置某些表头动态导出(可以根据筛选条件或一些属性的数据量)&#xff0c;方便导出后用户查看想看的信息。 一、技术选型&#xff1a; easyExcel的原生数据处理 二、方案设计&#xff1a; 根据EasyExcel支持的表头List<List<String>…...

深入探索 Elasticsearch 8:新特性与核心原理剖析(上)

深入探索 Elasticsearch 8&#xff1a;新特性与核心原理剖析 目录 一、引言 &#xff08;二&#xff09;版本 8 的重要意义 二、Elasticsearch 8 的新特性 三、Elasticsearch 的核心原理 一、引言 &#xff08;一&#xff09;Elasticsearch 简介 在大数据处理和搜索领域…...

瑜伽馆预约小程序,在线预约,提高商业价值

随着大众生活质量的提高&#xff0c;对休闲运动的关注逐渐加大&#xff0c;瑜伽作为一种身心放松、改善体态的运动&#xff0c;深受女性用户的喜爱。目前&#xff0c;各大瑜伽馆开始结合数字化&#xff0c;建立了新型的线上小程序&#xff0c;帮助大众快速预约体验瑜伽&#xf…...

Python--数据类型转换

在Python中&#xff0c;数据类型的转换是一个常见的操作&#xff0c;涉及将一种数据类型转换为另一种数据类型。Python提供了多种内置函数用于执行这种转换&#xff0c;如 int()、str()、float()、list()、tuple()、set()、dict() 等。下面详细讨论Python的基本数据类型及它们之…...

域控ntdsutil修改架构、域命名、PDC、RID、结构主机

#笔记记录# FSMO盒修改 1、提示访问特权不够&#xff0c;不能执行该操作&#xff0c;0x2098 清除缓存账号密码并修改新架构管理员账号密码即可。 背景&#xff1a;更替架构主机、域命名主机 C:\Windows\system32>ntdsutil ntdsutil: roles fsmo maintenance: ?? …...

解决 Swift 6 全局变量不能满足并发安全(concurrency-safe)读写的问题

概述 WWDC 24 终于在 Swift 十岁生日发布了全新的 Swift 6。这不仅意味着 Swift 进入了全新的“大”版本时代&#xff0c;而且 Swift 编译器终于做到了并发代码执行的“绝对安全”。 不过&#xff0c;从 Swift 5 一步迈入“新时代”的小伙伴们可能对新的并发检查有些许“水土不…...

迈入退休生活,全职开发ue独立游戏上架steam

决定退休了。算了算睡后收入&#xff0c;也可以达到每月一万一&#xff0c;正好可以养家糊口。 既然退休了&#xff0c;那就做些想做的事情&#xff0c;别人养花养草&#xff0c;而我打算开发独立游戏上架steam。 一&#xff0c;盘点下目前的技术体系。 1&#xff0c;图形学底…...

什么是光伏气象站——仁科测控

【仁科测控&#xff0c;品质保障】光伏气象站&#xff0c;‌这一专门为光伏发电系统设计的监测设备&#xff0c;‌其核心能力在于精确且实时地捕捉那些对光伏发电效率产生关键影响的气象因素。‌这些数据不仅为评估光伏电站的发电性能提供了重要依据&#xff0c;‌更是优化运维…...

webshell免杀--免杀入门

前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 本文主要整理webshell免杀的一些基础思路 入门级&#xff0c;不是很深入&#xff0c;主要是整理相关概念 免杀对象 1.各类杀毒软件 类似360&#xff0c;火绒等&#xff0c;查杀己方webshell的软件。 2.各类流量…...

Linux---02---系统目录及文件基本操作命令

课程回顾 操作系统 虚拟机安装 本章重点 Linux系统目录结构 常用命令 熟练区分Linux下各层目录的作用 熟练掌握Linux的常用命令&#xff08;文件命令、时间命令等&#xff09; 一、Linux系统目录结构 1.1 目录结构 /&#xff1a; 根目录&#xff0c;一般根目录下只存放…...

CSP-J/S第一轮初赛模拟赛试题

本模拟试题为本人自创&#xff0c;由于发布在 LG 所以就直接放入链接。 非经允许&#xff0c;不得转载。 本套模拟题只供大家练习使用&#xff0c;不保证难度与真实 CSP-J/S 完全符合。 本模拟赛为专业CSP类型的模拟赛&#xff0c;不存在错题、超出知识的题目。 CSP-J/S 20…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...