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

P3800 Power 收集和单调队列优化dp小总结

前言

历尽千辛万苦,终于在自己和老师的帮助下把P3800 Power 收集给过了,有一些trick要讲

P3800 Power

题目背景

据说在红雾异变时,博丽灵梦单身前往红魔馆,用十分强硬的手段将事件解决了。

然而当时灵梦在 Power 达到 MAX 之前,不具有“上线收点”的能力,所以她想要知道她能收集多少 P 点,然而这个问题她答不上来,于是她找到了学 OI 的你。

题目描述

可以把游戏界面理解成一个 \(N\)\(M\) 列的棋盘,有 \(K\) 个格子上有 P 点,其价值为 \(\operatorname{val}(i,j)\)

初始灵梦可以选择在第一行的任意一个格子出发,每秒她必须下移一格。

灵梦具有一个左右移动的速度 \(T\),可以使她每秒向左或右移动至多 \(T\) 格,也可以不移动,并且在单次移动中不能折返。移动可视为瞬间完成,不经过路途上的点,只能获得目标格子的 P 点。

求最终她能获得的所有 P 点的价值总和最大是多少?

输入格式

第一行四个整数,\(N,M,K,T\)

接下来 \(K\) 行每行 \(3\) 个整数 \(x,y,v\),代表第 \(x\) 行第 \(y\) 列有一个 \(\operatorname{val}\)\(v\) 的 P 点,数据保证一个格子上最多只有 \(1\) 个 P 点。

输出格式

一个整数,表示灵梦能获得的 P 点的价值总和的最大值。

输入输出样例 #1

输入 #1

3 3 4 1
1 1 3
1 2 1
2 2 3
3 3 3

输出 #1

9

说明/提示

对于 \(40\%\) 的测试点,\(1 \le N,M,T,K \le 200\)

对于 \(100\%\) 的测试点,\(1 \le N,M,T,K \le 4000\)\(0 \le v \le 100\)\(N,M,K,T\) 均为整数。

by-szc

思路

转移方程

\[dp[i][j]=max(dp[i-1][j-t],dp[i-1][j-t+1],...,dp[i-1][j+t])+a[i][j] \]

注意到题目支持\(O(mn)\)做法,以及移动区间的长度不变,且对于每一行的第i个值都是有上一行的\([i-t,i+t]\)区间的最大值转移过来的,类似滑动窗口,想到单调队列优化dp

可优化部分\(max(dp[i-1][j-t],dp[i-1][j-t+1],...,dp[i-1][j+t])\)

AC代码

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=4005;
int a[N][N];
int dp[N][N];
int main(){int n,m,k,t;cin>>n>>m>>k>>t;for(int i=1;i<=k;i++){int x,y,w;cin>>x>>y>>w;a[x][y]=w;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=-1e9;} }for(int i=1;i<=m;i++){dp[0][i]=0;}for(int i=1;i<=n;i++){int q[N];int l=1,r=0;int nxt=1;//维护下一个要选的点for(int j=1;j<=m;j++){int rim=min(m,j+t);//为了不让单调队列的右端点出界while(l<=r&&q[l]<j-t) l++;while(nxt<=rim){//没出界的点就选int pos=nxt;while(l<=r&&dp[i-1][q[r]]<=dp[i-1][pos]) r--;q[++r]=pos;nxt++;}if(l<=r) dp[i][j]=dp[i-1][q[l]]+a[i][j];}}int ans=0;for(int i=1;i<=m;i++){ans=max(ans,dp[n][i]);}cout<<ans;return 0;
}

总结重要!

继上一个题解P1725 琪露诺总结的要处理左端点可能出界的情况

而这一篇要处理右端点可能出界的情况集齐龙珠

预防左端点出界处理方法
for(int i=L;i<=n;i++){//令i=Lwhile(l<=r&&q[l]+R<i) l++;while(l<=r&&dp[q[r]]<=dp[i-L]) r--;//因为要是这里的i-L>=0所以上两行的i要从L开始q[++r]=i-L;dp[i]=dp[q[l]]+a[i];if(i+R>n){ans=max(ans,dp[i]);}}
预防右端点出界处理方法
int q[N];
int l=1,r=0;
int nxt=1;//维护下一个要选的点
for(int j=1;j<=m;j++){int rim=min(m,j+t);//为了不让单调队列的右端点出界while(l<=r&&q[l]<j-t) l++;while(nxt<=rim){//没出界的点就选int pos=nxt;while(l<=r&&dp[i-1][q[r]]<=dp[i-1][pos]) r--;q[++r]=pos;nxt++;}if(l<=r) dp[i][j]=dp[i-1][q[l]]+a[i][j];
}

剩下交给刷题吧

http://www.hskmm.com/?act=detail&tid=31495

相关文章:

  • 微信群机器人接口
  • 2025 年杭州品牌策划公司机构推荐榜:餐饮品牌策划/家电品牌策划聚焦实战力与适配性,这家杭州本土机构值得关注
  • 2025 年土工格栅厂家推荐榜:聚焦工程适配与品质保障,优选山东大成工程材料有限公司
  • 2025年液压阀块厂家最新权威推荐榜:液压阀/阀块加工/阀块零件机加工专业制造商,技术实力与市场口碑深度解析
  • logging模块用法
  • 软件服务行业,被玩坏了的阿米巴
  • 实用指南:WordPress提速指南:Memcached+Super Static Cache+CDN缓存网站内容
  • AI元人文中价值原语博弈系统的理论建构与实践意义探析
  • LGP3201 [HNOI 2009] 梦幻布丁 学习笔记
  • 2025年石头纸设备/吹塑机厂家最新权威推荐榜:环保石头纸、碳酸钙石头纸、固废石头纸及挤出吹塑机、注射吹塑机、半导体清洗液瓶子吹塑机专业选购指南
  • AI技术新突破:图像编辑与浏览器智能体
  • PWN手的成长之路-16-OGeek2019-babyrop
  • 2025年掘进机厂家最新权威推荐榜:隧道掘进机、煤矿掘进机、岩石掘进机、盾构掘进机,专业实力与高效施工口碑之选
  • AI元人文:关于“价值原语博弈”的对话
  • 2025/10/15
  • 2025年冷却塔厂家最新权威推荐榜单:工业冷却塔、闭式冷却塔、横流式冷却塔、逆流式冷却塔专业制造商精选
  • 2025年法兰保护套厂家最新推荐排行榜:管道法兰保护罩,不锈钢法兰保护套,耐腐蚀法兰保护套公司精选
  • 2025年扒胎机厂家最新权威推荐榜:液压无损扒胎机,全自动扒胎机,汽保扒胎机,轮胎扒胎机,汽车扒胎机,大轮胎扒胎机,无损扒胎机,辽南扒胎机,小车扒胎机,立式扒胎机专业选购指南
  • 2025年中国太阳能板品牌TOP10(排行榜):格局巨变
  • 【第十五周】机器学习的学习笔记11 - 实践
  • 2025年冲压件厂家最新权威推荐榜:新能源/光伏/精密/异形/五金/铝/汽配/不锈钢/家具冲压件源头厂商实力解析
  • 2025年无锡公考考编培训机构最新权威推荐榜:事业单位/央企国企招录培训实力厂家精选指南
  • 2025年重庆短视频代运营与百度信息流推广公司综合推荐榜,拍摄/投流/获客/引流/剪辑/包年推广哪家好?
  • 2025年重庆短视频信息流投流/获客/巨量广告投放/拍摄/代运营推广公司推荐榜区域精选公司分享
  • 俄罗斯合作伙伴 Mobx,用 NocoBase 交付多场景方案
  • 2025年法兰罩厂家最新权威推荐榜:专业防护与精密制造,工业管道安全守护首选品牌
  • 2025 年公务员培训机构推荐榜:聚焦适配与服务,认准靠谱选择
  • IDM(Internet Download Managerv 6.38)破解版下载!IDM 下载器永久免费版!提升下载速度达5倍!安装及使用教程
  • 2025年数控滚齿机厂家最新权威推荐榜:高精度齿轮加工设备源头供应商,实力与口碑双重保障
  • 2025年太阳能板定制厂家终极推荐榜:揭秘 top 10 可靠选择