题解：AtCoder AT_awc0048_b Footsteps in the Hallway

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderB - Footsteps in the Hallway【题目描述】Takahashi is trying to walk through a long corridor consisting ofN NNtiles arranged in a row. The tiles are numbered from left to right as Tile1 11, Tile2 22,… \ldots…, TileN NN.高桥正试图穿过一条由N NN块地砖排成一行组成的长廊。地砖从左到右编号为地砖1 11、地砖2 22、……、地砖N NN。Each tile is covered with dust. Initially, Tilei iihas dust of thicknessH i H_iHi​. When Takahashi steps on Tilei ii, the dust thickness on that tile becomesmax ⁡ ( 0 , H i − D i ) \max(0,\; H_i - D_i)max(0,Hi​−Di​), whereD i D_iDi​is a non-negative integer defined for Tilei ii. The dust thickness on tiles that Takahashi does not step on remains unchanged at the initial thicknessH i H_iHi​.每块地砖上都覆盖着灰尘。初始时地砖i ii的灰尘厚度为H i H_iHi​。当高桥踩在地砖i ii上时该地砖的灰尘厚度变为max ⁡ ( 0 , H i − D i ) \max(0,\; H_i - D_i)max(0,Hi​−Di​)其中D i D_iDi​是定义在地砖i ii上的非负整数。高桥没有踩到的地砖的灰尘厚度保持不变仍为初始厚度H i H_iHi​。Takahashi starts at Tile1 11, and TileN NNis the goal. Takahashi always moves only to the right. Specifically, when he is currently on Tilej jj, he can choose Tilej 1 j1j1or Tilej 2 j2j2as his next destination. However, he cannot move beyond TileN NN(he can move to Tilej 1 j1j1only ifj 1 ≤ N j1 \leq Nj1≤N, and to Tilej 2 j2j2only ifj 2 ≤ N j2 \leq Nj2≤N). Takahashi steps on a tile upon arriving at it. He also steps on Tile1 11, the starting point. Takahashi ends his movement upon reaching TileN NN.高桥从地砖1 11出发地砖N NN是目标。高桥始终只向右移动。具体来说当他当前位于地砖j jj时他可以选择地砖j 1 j1j1或地砖j 2 j2j2作为下一个目的地。但是他不能移动到地砖N NN之外只有当j 1 ≤ N j1 \leq Nj1≤N时才能移动到地砖j 1 j1j1只有当j 2 ≤ N j2 \leq Nj2≤N时才能移动到地砖j 2 j2j2。高桥在到达地砖时踩在上面。他也会踩在起点地砖1 11上。高桥在到达地砖N NN时结束移动。Due to the above movement rules, Tile1 11and TileN NNare always stepped on. Also, since Takahashi always moves to the right, he never steps on the same tile more than once.根据上述移动规则地砖1 11和地砖N NN总是会被踩到。此外由于高桥始终向右移动他永远不会踩到同一块地砖超过一次。After Takahashi walks through the corridor, Aoki inspects the corridor and counts the number oftiles with footprints. A footprint is left on Tilei iiif the dust thickness on Tilei iiafter Takahashi’s movement is strictly less than the initial thicknessH i H_iHi​.高桥穿过长廊后青木检查了长廊并统计了留有脚印的地砖数量。如果地砖i ii在高桥移动后的灰尘厚度严格小于初始厚度H i H_iHi​则该地砖上留有脚印。If Takahashi did not step on Tilei ii, the dust thickness remainsH i H_iHi​, so no footprint is left.如果高桥没有踩到地砖i ii灰尘厚度仍为H i H_iHi​因此不会留下脚印。If Takahashi stepped on Tilei ii, the dust thickness becomesmax ⁡ ( 0 , H i − D i ) \max(0,\; H_i - D_i)max(0,Hi​−Di​). This is strictly less thanH i H_iHi​if and only ifH i 0 H_i 0Hi​0andD i 0 D_i 0Di​0. Therefore, ifH i 0 H_i 0Hi​0orD i 0 D_i 0Di​0, no footprint is left even if the tile is stepped on.如果高桥踩到了地砖i ii灰尘厚度变为max ⁡ ( 0 , H i − D i ) \max(0,\; H_i - D_i)max(0,Hi​−Di​)。这严格小于H i H_iHi​当且仅当H i 0 H_i 0Hi​0且D i 0 D_i 0Di​0。因此如果H i 0 H_i 0Hi​0或D i 0 D_i 0Di​0即使踩到该地砖也不会留下脚印。Takahashi wants to minimize the number of tiles with footprints. Find the minimum number of tiles with footprints when Takahashi moves along an optimal path.高桥希望最小化留有脚印的地砖数量。求高桥沿着最优路径移动时留有脚印的地砖的最小数量。【输入】N NNH 1 H_1H1​H 2 H_2H2​⋯ \cdots⋯H N H_NHN​D 1 D_1D1​D 2 D_2D2​⋯ \cdots⋯D N D_NDN​The first line contains an integerN NN, the number of tiles.The second line containsN NNintegersH 1 , H 2 , … , H N H_1, H_2, \ldots, H_NH1​,H2​,…,HN​separated by spaces, representing the initial dust thickness of each tile.The third line containsN NNintegersD 1 , D 2 , … , D N D_1, D_2, \ldots, D_ND1​,D2​,…,DN​separated by spaces, representing the upper bound of dust reduction when each tile is stepped on.【输出】Print in one line the minimum number of tiles with footprints when Takahashi moves optimally.【输入样例】5 3 0 5 2 4 1 1 1 1 1【输出样例】3【算法标签】#线性DP-一维#【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;intn;// 数组长度inth[N],d[N];// h数组和d数组intdp[N];// 动态规划数组// 计算位置x的代价intcost(intx){// 如果h[x]和d[x]都大于0代价为1否则为0if(h[x]0d[x]0){return1;}else{return0;}}intmain(){cinn;// 读取数组长度// 读取h数组for(inti1;in;i){cinh[i];}// 读取d数组for(inti1;in;i){cind[i];}// 初始化dp数组为无穷大memset(dp,0x3f,sizeof(dp));// 初始化前两个位置的dp值dp[1]cost(1);dp[2]cost(1)cost(2);// 动态规划转移for(inti3;in;i){dp[i]min(dp[i-1],dp[i-2])cost(i);}// 输出结果coutdp[n]endl;return0;}【运行结果】5 3 0 5 2 4 1 1 1 1 1 3