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

· · 题解

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

题目概括

有一个 n 行 m 列的矩阵，每行格子的数值都由 1 \sim m 构成。有一个机器人在 (1,1) 的位置，他会循环执行下列操作：

  1. 在 x 行时以自身位置向左和向右数 k_x 个格子，移动到其中数值最大的格子上。
  2. 向下移动一格，保持列数不变，直到超出矩阵最后一行。

可以自由组合每行的元素，使得机器人经过的格子数值之和最小，求出这个值。

思路

下面是说明过程，如果赶时间就直接看结论吧。

首先，对于每次向下移动后，因为每行格子的数值都是 \ge 1 的，所以想要取到 1，就必须在刚移到新行时就经过 1。

其次，由于机器人每次都会在自己左边 k_x 个格子和自己右边 k_x 个格子中寻找最大的数值，所以我们只需要将最小的几个数放到机器人的左右，每次就可以取到最小值。

可以看出来我们每次横向移动答案都是加上 s + 1（s 是可遍历的格子个数）。

而在横向移动时是有多个可移动的点位的，但是我们为了使得每次机器人遍历到的区间最小，需要移动到最靠近边界的地方。

结论

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

    代码

    其他小细节都标注在注释里了。

    
#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; }



如果有不会的部分可以试着以我的方法推导一下样例，过一遍就会了。