当前位置: 首页 > 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;
}

http://www.lryc.cn/news/427589.html

相关文章:

  • 【图像处理】在图像处理算法开发中,有哪些常见的主观评价指标和客观评价指标?
  • 从零开始学cv-6:图像的灰度变换
  • 使用Apache POI和POI-OOXML实现word模板文档自动填充功能
  • 【HarmonyOS NEXT星河版开发学习】综合测试案例-各平台评论部分
  • 垂直行业数字化表现抢眼 亚信科技全年利润展望乐观
  • EmguCV学习笔记 VB.Net 4.1 颜色变换
  • 【MySQL进阶之路】表结构的操作
  • 3分钟搞定PDF转PPT!你一定要知道的3款转换神器!
  • 【EasyExcel】导出excel-设置动态表头并导出数据
  • 深入探索 Elasticsearch 8:新特性与核心原理剖析(上)
  • 瑜伽馆预约小程序,在线预约,提高商业价值
  • Python--数据类型转换
  • 域控ntdsutil修改架构、域命名、PDC、RID、结构主机
  • 解决 Swift 6 全局变量不能满足并发安全(concurrency-safe)读写的问题
  • 迈入退休生活,全职开发ue独立游戏上架steam
  • 什么是光伏气象站——仁科测控
  • webshell免杀--免杀入门
  • Linux---02---系统目录及文件基本操作命令
  • CSP-J/S第一轮初赛模拟赛试题
  • LangGPT结构化提示词
  • 如何为个人网站更换ssl证书
  • RabbitMQ-消息队列延迟队列一
  • JavaScript中普通对象和Map对象的区别
  • Liunx搭建Rustdesk远程桌面服务
  • antv X6--实现节点旁添加多个text标签
  • JAVA--多线程
  • ADB-DROM
  • mysql 之 explain
  • CentOS迁移案例 | 保障轨道交通安全、发挥基础设施效能,麒麟信安操作系统支撑某市轨道交通畅行无忧
  • 获取操作系统的信息(Go语言)