专栏文章

题解:P13993 【MX-X19-T2】「LAOI-14」SPECIALZ

P13993题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minzle8l
此快照首次捕获于
2025/12/02 10:56
3 个月前
此快照最后确认于
2025/12/02 10:56
3 个月前
查看原文

P13993 【MX-X19-T2】「LAOI-14」SPECIALZ

题目概括

有一个 nnmm 列的矩阵,每行格子的数值都由 1m1 \sim m 构成。有一个机器人在 (1,1)(1,1) 的位置,他会循环执行下列操作:
  1. xx 行时以自身位置向左和向右数 kxk_x 个格子,移动到其中数值最大的格子上。
  2. 向下移动一格,保持列数不变,直到超出矩阵最后一行。
可以自由组合每行的元素,使得机器人经过的格子数值之和最小,求出这个值。

思路

下面是说明过程,如果赶时间就直接看结论吧。
首先,对于每次向下移动后,因为每行格子的数值都是 1\ge 1 的,所以想要取到 11,就必须在刚移到新行时就经过 11
其次,由于机器人每次都会在自己左边 kxk_x 个格子和自己右边 kxk_x 个格子中寻找最大的数值,所以我们只需要将最小的几个数放到机器人的左右,每次就可以取到最小值。
可以看出来我们每次横向移动答案都是加上 s+1s + 1ss 是可遍历的格子个数)。
而在横向移动时是有多个可移动的点位的,但是我们为了使得每次机器人遍历到的区间最小,需要移动到最靠近边界的地方

结论

  1. 每到一个新的行,ansans+1ans \gets ans + 1
  2. 计算左右可遍历的格子数量 ss,更新答案 ansans+s+1ans \gets ans + s + 1
  3. 在左右可遍历的最远格子中选择最靠近边界的格子,更新位置。

代码

其他小细节都标注在注释里了。
CPP
#include <bits/stdc++.h>
using namespace std;

int n,m;
long long ans;		//这里一定要 long long 哦~ 
int pos=1;		//初始位置 1
int k[500005];

int main(){
	cin >> n >> m;
	for (int i=1;i<=n;i++)		//读入每行的 k 
		cin >> k[i];
	for (int i=1;i<=n;i++){
		int l=1,r=m;		//这里其实不必要,看着好看 
		int sl,sr,s;		//左右可遍历的格子数量和总的数量 
		int nposl,nposr;		//左右最远达到的位置 
		sl=min(pos-l,k[i]);		//计算数量,不超边界 
		sr=min(r-pos,k[i]);		//同上 
		s=sl+sr;
		ans+=1;		//每次换行都 +1 
		ans+=s+1;		//计算横向移动答案 
		if (sl==0)		//已经在边界的时候不能原地不动 
			nposl=pos+1;
		else
			nposl=pos-sl;
		if (sr==0)		//同上 
			nposr=pos-1;
		else
			nposr=pos+sr;
		if (nposl-l<r-nposr)		//看哪个离边界近 
			pos=nposl;		//更新位置 
		else
			pos=nposr;		//更新位置 
	}
	cout << ans;		//输出答案 
	return 0;
}
如果有不会的部分可以试着以我的方法推导一下样例,过一遍就会了。

评论

0 条评论,欢迎与作者交流。

正在加载评论...