{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e\u003c!DOCTYPE HTML PUBLIC \"-//W3C//DTD HTML 4.01 Transitional//EN\"\u003e\u003chtml\u003e\u003chead\u003e\u003cMETA http-equiv\u003d\"Content-Type\" content\u003d\"text/html; charset\u003dutf-8\" /\u003e\u003c/head\u003e\u003cbody\u003e\u003c/body\u003e\u003c/html\u003e\u003c/!doctype\u003e\u003c/p\u003e\n\u003cdiv\u003e\n\u003cp\u003e\n 我们著名的编程黑帮来到了这个城市。\u003ci\u003eFarzi Coder\u003c/i\u003e 是这里的头目。他在他的帮派中雇佣了一个新成员,名叫 \u003ci\u003eLambu Keyboard\u003c/i\u003e。\u003ci\u003eFarzi Coder\u003c/i\u003e 非常聪明(至少他是这么认为的),所以他想测试 \u003ci\u003eLambu Keyboard\u003c/i\u003e 的编程技能。他给了他这个任务:\n \u003c/p\u003e\n\n\u003cp\u003e 有 n 栋建筑(从左到右编号),高度分别为 H\u003csub\u003e1\u003c/sub\u003e, H\u003csub\u003e2\u003c/sub\u003e...H\u003csub\u003en\u003c/sub\u003e。你可以从任何一栋建筑开始跳跃。\u003c/p\u003e\n\u003cp\u003e\n 跳跃的规则是:\n \u003c/p\u003e\n\u003col\u003e\n\u003cli\u003e 你只能跳到比当前建筑高度低的建筑上。\u003c/li\u003e\n\u003cli\u003e 在第一次跳跃时可以向任意方向跳,第二次跳跃必须朝着与上一次跳跃相反的方向,并且必须在当前索引与上一个索引之间结束,即如果我们从建筑 5 开始跳跃,最初可以向任意方向跳。假设我们跳到建筑 8,那么在下一次跳跃中我们只能向左跳,并且只能在索引 6 和 7 的建筑上跳。假设我们跳到建筑 6,那么下一次我们只能向右跳,并且在 6 和 8 之间,即跳到 7。\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003e 我们需要找出他可以进行的最大跳跃次数,考虑每栋建筑作为起点。\u003c/p\u003e\n\u003ch2\u003e输入\u003c/h2\u003e\n\u003cp\u003e 第一行包含一个整数 \u003cb\u003en\u003c/b\u003e,即建筑的数量。\u003cbr /\u003e\u003cbr /\u003e\n 第二行包含 n 个用空格分隔的整数,表示从 1 到 n 的建筑高度。\u003c/p\u003e\n\u003ch2\u003e输出\u003c/h2\u003e\n\u003cp\u003e 一行包含 n 个整数,第 i\u003csup\u003eth\u003c/sup\u003e 个整数表示从第 i\u003csup\u003eth\u003c/sup\u003e 栋建筑开始的最大跳跃次数。\u003c/p\u003e\n\u003ch2\u003e约束条件\u003c/h2\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003e1 ≤ n ≤ 5000\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1 ≤ H\u003csub\u003e1\u003c/sub\u003e, H\u003csub\u003e2\u003c/sub\u003e ... H\u003csub\u003en\u003c/sub\u003e ≤ 10000\u003c/b\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch2\u003e示例\u003c/h2\u003e\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cpre\u003e5\n1 3 4 2 5\n \u003c/pre\u003e\u003ch3\u003e输出\u003c/h3\u003e\n\u003cpre\u003e0 1 1 1 2\n \u003c/pre\u003e\u003ch3\u003e解释\u003c/h3\u003e\n\u003cp\u003e 如果起始建筑的高度为 1,则无法跳到任何其他建筑。\u003cbr /\u003e\u003cbr /\u003e\n 如果起始建筑的高度为 3,则可以跳到右边高度为 2 的建筑或左边高度为 1 的建筑。但最多只能跳一次。\u003cbr /\u003e\u003cbr /\u003e\n 如果起始建筑的高度为 5,则一个可能的最佳序列是跳到高度为 3 的建筑,然后跳到高度为 2 的建筑。所以最大跳跃次数为 2。\u003cbr /\u003e \u003c/p\u003e\n\u003c/div\u003e\n\u003cp\u003e\u003c/p\u003e"}}]}