打卡信奥刷题（2763）用C++实现信奥题 P3800 Power 收集-开发者社区

P3800 Power 收集

题目背景

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

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

题目描述

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

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

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

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

输入格式

第一行四个整数，N , M , K , T N,M,K,TN,M,K,T。

接下来K KK行每行3 33个整数x , y , v x,y,vx,y,v，代表第x xx行第y yy列有一个val ⁡ \operatorname{val}val为v vv的 P 点，数据保证一个格子上最多只有1 11个 P 点。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

说明/提示

对于40 % 40\%40%的测试点，1 ≤ N , M , T , K ≤ 200 1 \le N,M,T,K \le 2001≤N,M,T,K≤200。

对于100 % 100\%100%的测试点，1 ≤ N , M , T , K ≤ 4000 1 \le N,M,T,K \le 40001≤N,M,T,K≤4000，0 ≤ v ≤ 100 0 \le v \le 1000≤v≤100，N , M , K , T N,M,K,TN,M,K,T均为整数。

by-szc

C++实现

#include<bits/stdc++.h>usingnamespacestd;#defineMAXN4010inttail=0,head=1;intn,m,k,t,ans;intq[MAXN],a[MAXN][MAXN],dp[MAXN][MAXN];voidqueue_empty(){//清空窗口tail=0,head=1;}voidswi(intx,intlast){//插入元素if(x+t<=m){//判断是否超过边界,不加会REwhile(dp[last][x+t]>dp[last][q[tail]]&&tail>=head){//单调队列tail--;}q[++tail]=x+t;}while(q[head]+t<x)head++;}voidswp(intlast){//初始化窗口for(inti=1;i<=t;i++){while(dp[last][i]>dp[last][q[tail]]&&tail>=head){tail--;}q[++tail]=i;}}intmain(){scanf("%d%d%d%d",&n,&m,&k,&t);for(inti=1;i<=k;i++){intx,y,z;scanf("%d%d%d",&x,&y,&z);a[x][y]=z;}for(inti=1;i<=n;i++){//第一行初始化dp[1][i]=a[1][i];}for(inti=2;i<=n;i++){swp(i-1);for(intj=1;j<=m;j++){swi(j,i-1);dp[i][j]=dp[i-1][q[head]]+a[i][j];}queue_empty();}for(inti=1;i<=m;i++){ans=max(dp[n][i],ans);}cout<<ans;}