热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

计蒜客T31434广场车神(二维前缀和优化dp)

题目链接Reference:https:www.cnblogs.comdiltheyp9757781.html首先容易想到的常规dp是,初始化dp(i,j)0dp(i,j)0dp(

题目链接



Reference:https://www.cnblogs.com/dilthey/p/9757781.html

首先容易想到的常规dp是,初始化dp(i,j)=0dp(i,j)=0,对于当前下标(i,j)(i,j)为右上角的一个边长为k+1k+1的正方形内:

dp(i,j)=∑x=i−ki∑y=j−kjdp(x,y)dp(i,j)= \sum_{x=i-k}^{i} \sum_{y=j-k}^{j}dp(x,y)

但是这样的时间复杂度为O(nwk2)O(nwk^2),使用二维前缀和优化

设最后dp方程的二维前缀和sum(i,j)=∑x=1i∑y=1jdp(x,y)sum(i,j)= \sum_{x=1}^{i} \sum_{y=1}^{j}dp(x,y),因为当前状态只能从一个(k+1)∗(k+1)(k+1)*(k+1)的正方形内的状态转移,如果使用二维前缀和计算这一方形区域,设下边界为d=i−k−1d=i-k-1,左边界为l=j−k−1l=j-k-1,状态转移方程为:

dp(i,j)=(sum(i−1,j)+sum(i,j−1)−sum(i−1,j−1))−(sum(d,j)+sum(i,l)−sum(d,l))dp(i,j)=(sum(i-1,j)+sum(i,j-1)−sum(i-1,j-1))−(sum(d,j)+sum(i,l)−sum(d,l)),画个图很容易看出来,然后根据二维前缀和的定义:

sum(i,j)=(sum(i−1,j)+sum(i,j−1)−sum(i−1,j−1))+dp(i,j)=2(sum(i−1,j)+sum((i,j−1)−sum(i−1,j−1))−(sum(d,j)+sum(i,l)−sum(d,l))sum(i,j)=(sum(i-1,j)+sum(i,j-1)−sum(i-1,j-1))+dp(i,j)=2(sum(i-1,j)+sum((i,j-1)−sum(i-1,j-1))−(sum(d,j)+sum(i,l)−sum(d,l))

那么最后的答案就是:

dp(n,m)=sum(n,m)−(sum(n−1,m)+sum(n,m−1)−sum(n−1,m−1))dp(n,m)=sum(n,m)−(sum(n-1,m)+sum(n,m-1)−sum(n-1,m-1))

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=998244353;
const int maxn=2e5+10;
ll sum[2020][2020];
int main(){
freopen("racing.in","r",stdin);
freopen("racing.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m,k;
cin>>n>>m>>k;
sum[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(i==1 && j==1) continue;
int l=max(0,i-k-1),d=max(0,j-k-1);
sum[i][j]=(2*(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1])%Mod-(sum[l][j]+sum[i][d]-sum[l][d])%Mod+Mod)%Mod;
}
ll ans=(sum[n][m]-(sum[n-1][m]+sum[n][m-1]-sum[n-1][m-1])%Mod+Mod)%Mod;
cout<<ans<<endl;
return 0;
}

本文地址:https://blog.csdn.net/qq_44691917/article/details/107441455



推荐阅读
  • 深入解析ESFramework中的AgileTcp组件
    本文详细介绍了ESFramework框架中AgileTcp组件的设计与实现。AgileTcp是ESFramework提供的ITcp接口的高效实现,旨在优化TCP通信的性能和结构清晰度。 ... [详细]
  • 本题来自WC2014,题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系,要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]
  • 本题要求在一组数中反复取出两个数相加,并将结果放回数组中,最终求出最小的总加法代价。这是一个经典的哈夫曼编码问题,利用贪心算法可以有效地解决。 ... [详细]
  • 本文介绍了如何利用 Spring Boot 和 Groovy 构建一个灵活且可扩展的动态计算引擎,以满足钱包应用中类似余额宝功能的推广需求。我们将探讨不同的设计方案,并最终选择最适合的技术栈来实现这一目标。 ... [详细]
  • 在项目部署后,Node.js 进程可能会遇到不可预见的错误并崩溃。为了及时通知开发人员进行问题排查,我们可以利用 nodemailer 插件来发送邮件提醒。本文将详细介绍如何配置和使用 nodemailer 实现这一功能。 ... [详细]
  • 采用IKE方式建立IPsec安全隧道
    一、【组网和实验环境】按如上的接口ip先作配置,再作ipsec的相关配置,配置文本见文章最后本文实验采用的交换机是H3C模拟器,下载地址如 ... [详细]
  • 丽江客栈选择问题
    本文介绍了一道经典的算法题,题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈,并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]
  • JSOI2010 蔬菜庆典:树结构中的无限大权值问题
    本文探讨了 JSOI2010 的蔬菜庆典问题,主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性,提出了有效的解决方案,并详细解释了算法的实现过程。 ... [详细]
  • 目录一、salt-job管理#job存放数据目录#缓存时间设置#Others二、returns模块配置job数据入库#配置returns返回值信息#mysql安全设置#创建模块相关 ... [详细]
  • 2018-2019学年第六周《Java数据结构与算法》学习总结
    本文总结了2018-2019学年第六周在《Java数据结构与算法》课程中的学习内容,重点介绍了非线性数据结构——树的相关知识及其应用。 ... [详细]
  • Coursera ML 机器学习
    2019独角兽企业重金招聘Python工程师标准线性回归算法计算过程CostFunction梯度下降算法多变量回归![选择特征](https:static.oschina.n ... [详细]
  • 本文深入探讨了SQL数据库中常见的面试问题,包括如何获取自增字段的当前值、防止SQL注入的方法、游标的作用与使用、索引的形式及其优缺点,以及事务和存储过程的概念。通过详细的解答和示例,帮助读者更好地理解和应对这些技术问题。 ... [详细]
  • 探讨ChatGPT在法律和版权方面的潜在风险及影响,分析其作为内容创造工具的合法性和合规性。 ... [详细]
  • 优化SQL Server批量数据插入存储过程的实现
    本文介绍了一种改进的SQL Server存储过程,用于生成批量插入语句。该方法不仅提高了性能,还支持单行和多行模式,适用于SQL Server 2005及以上版本。 ... [详细]
  • 软件工程课堂测试2
    要做一个简单的保存网页界面,首先用jsp写出保存界面,本次界面比较简单,首先是三个提示语,后面是三个输入框,然 ... [详细]
author-avatar
淑敏小朋友
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有