P3800 Power 收集
题目背景
据说在红雾异变时，博丽灵梦单身前往红魔馆，用十分强硬的手段将事件解决了。
然而当时灵梦在 Power 达到 MAX 之前，不具有“上线收点”的能力，所以她想要知道她能收集多少 P 点，然而这个问题她答不上来，于是她找到了学 OI 的你。
题目描述
可以把游戏界面理解成一个
N
N
N 行
M
M
M 列的棋盘，有
K
K
K 个格子上有 P 点，其价值为
val
(
i
,
j
)
\\operatorname{val}(i,j)
val(i,j)。
初始灵梦可以选择在第一行的任意一个格子出发，每秒她必须下移一格。
灵梦具有一个左右移动的速度
T
T
T，可以使她每秒向左或右移动至多
T
T
T 格，也可以不移动，并且在单次移动中不能折返。移动可视为瞬间完成，不经过路途上的点，只能获得目标格子的 P 点。
求最终她能获得的所有 P 点的价值总和最大是多少？
输入格式
第一行四个整数，
N
,
M
,
K
,
T
N,M,K,T
N,M,K,T。
接下来
K
K
K 行每行
3
3
3 个整数
x
,
y
,
v
x,y,v
x,y,v，代表第
x
x
x 行第
y
y
y 列有一个
val
\\operatorname{val}
val 为
v
v
v 的 P 点，数据保证一个格子上最多只有
1
1
1 个 P 点。
输出格式
一个整数，表示灵梦能获得的 P 点的价值总和的最大值。
输入输出样例 #1
输入 #1
3 3 4 1
1 1 3
1 2 1
2 2 3
3 3 3
输出 #1
9
说明/提示
对于
40
%
40\\%
40% 的测试点，
1
≤
N
,
M
,
T
,
K
≤
200
1 \\le N,M,T,K \\le 200
1≤N,M,T,K≤200。
对于
100
%
100\\%
100% 的测试点，
1
≤
N
,
M
,
T
,
K
≤
4000
1 \\le N,M,T,K \\le 4000
1≤N,M,T,K≤4000，
0
≤
v
≤
100
0 \\le v \\le 100
0≤v≤100，
N
,
M
,
K
,
T
N,M,K,T
N,M,K,T 均为整数。
by-szc
C++实现
#include<cstdio>
#include<ctype.h>
#include<cstring>
#define int long long
#define max(a,b) a>b?a:b
const int MARX = 4e3+10;
int n,m,k,t, now,ans;
int f[MARX][MARX];
int head=1,tail=1;//手写双端队列
int q[MARX]={9223372036854775807};//为q[0]赋一个极大值,来防止插入元素时越界
inline int read(){
int fl=1,w=0;char ch=getchar();
while(!isdigit(ch) && ch!='-') ch=getchar();
if(ch=='-') fl=–1;
while(isdigit(ch)){w=w*10+ch–'0',ch=getchar();}
return fl*w;
}
void in(int x){
while(f[now–1][x]>f[now–1][q[tail]] && tail>=head)
tail—;//取出队尾小于插入元素的数 , 以保证单调性
q[++tail]=x;//插入队尾
}
int find(int x){
if(x+t<=m)in(x+t);//将能转移到x点 的 最后一个元素 x+t 插入队列
while(q[head]+t<x) head++;//找到队首第一个能够转移到x的点
return q[head];
}
signed main(){
n=read(),m=read(),k=read(),t=read();
while(k—){
int x=read(),y=read(),w=read();
f[x][y]=w;
}
for(now=2;now<=n;now++){
for(int i=1;i<=t;i++) in(i);//初始化单调队列 , 满足能够 转移j=1的点
for(int j=1;j<=m;j++) f[now][j]+=f[now–1][find(j)];// 进行转移
head=tail=1 , q[1]=0;//清空队列
}
for(int i=1;i<=m;i++)//取得最大值
ans=max(ans,f[n][i]);
printf("%lld",ans);
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
