{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e阅读题目的简体中文版本\u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/OCT15/mandarin/JUMP.pdf\"\u003eMandarin Chinese\u003c/a\u003e和\u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/OCT15/russian/JUMP.pdf\"\u003eRussian\u003c/a\u003e\u003c/h3\u003e\n\n\n\u003cp\u003e\n主厨Chef正在参加一个山地跳跃比赛。\n\u003c/p\u003e\n\u003cp\u003e\n有N座山排成一排,每座山都被分配了从1到\u003cb\u003eN\u003c/b\u003e的唯一索引 — 第\u003cb\u003ei\u003c/b\u003e座山上有一个索引\u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e。第\u003cb\u003ei\u003c/b\u003e座山的高度是\u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e。\nChef从第一座山开始,目标是通过从左到右跳过山脉,到达第\u003cb\u003eN\u003c/b\u003e座山(他不允许向另一个方向跳跃),从第\u003cb\u003ei\u003c/b\u003e座山跳到第\u003cb\u003ej\u003c/b\u003e座山的能量消耗为(\u003cb\u003eH\u003csub\u003ej\u003c/sub\u003e\u003c/b\u003e - \u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e)\u003csup\u003e2\u003c/sup\u003e。\n\u003c/p\u003e\n\u003cp\u003e\n当主厨在第\u003cb\u003ei\u003c/b\u003e座山时,他必须为该山的社区准备一道特别的菜,以感谢他们让他使用他们的资源。这将消耗他\u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e的能量(一些菜是主厨的最爱,准备它会让主厨恢复精力,因此\u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e可能是负数)。为了让主厨Chef面临更大的挑战,他只能从第\u003cb\u003ei\u003c/b\u003e座山跳到第\u003cb\u003ej\u003c/b\u003e座山,当且仅当\u003cb\u003ei \u003c j\u003c/b\u003e且\u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e \u003c P\u003csub\u003ej\u003c/sub\u003e\u003c/b\u003e。\n\u003c/p\u003e\n\u003cp\u003e\n帮助Chef选择跳跃顺序,使能量消耗最小。(注意,在任何时刻,能量消耗可能是负数。)\n\u003c/p\u003e\n\n\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cp\u003e\n输入的第一行包含一个整数\u003cb\u003eN\u003c/b\u003e。\u003cbr /\u003e\n第二行包含\u003cb\u003eN\u003c/b\u003e个以空格分隔的整数\u003cb\u003eP\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eP\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ... , \u003cb\u003eP\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e。\u003cbr/\u003e\n第三行包含\u003cb\u003eN\u003c/b\u003e个以空格分隔的整数\u003cb\u003eA\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eA\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ... , \u003cb\u003eA\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e。\u003cbr/\u003e\n第四行包含\u003cb\u003eN\u003c/b\u003e个以空格分隔的整数\u003cb\u003eH\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eH\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ... , \u003cb\u003eH\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e。\u003cbr/\u003e\n\u003c/p\u003e\n\n\u003ch3\u003e输出\u003c/h3\u003e\n\u003cp\u003e输出一行,包含问题的答案,即\u003cb\u003e消耗\u003c/b\u003e的最小可能能量。\u003c/p\u003e\n\n\u003ch3\u003e约束\u003c/h3\u003e\n\u003cp\u003e\u003cul\u003e\n\u003cli\u003e\u003cb\u003e2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e3 × 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003eP\u003c/b\u003e是前\u003cb\u003eN\u003c/b\u003e个整数的排列\u003c/li\u003e\n\u003cli\u003e\u003cb\u003eP\u003csub\u003e1\u003c/sub\u003e\u003d1\u003c/b\u003e且\u003cb\u003eP\u003csub\u003eN\u003c/sub\u003e\u003dN\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e-10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e ≤ \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003e6 × 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003c/ul\u003e\u003c/p\u003e\n\n\u003ch3\u003e子任务\u003c/h3\u003e\n\u003cp\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003e子任务 1\u003c/b\u003e (5 分) : \u003cb\u003e2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e20\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e子任务 2\u003c/b\u003e (15 分) : \u003cb\u003e2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e5000\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e子任务 3\u003c/b\u003e (20 分) : \u003cb\u003e2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e3 × 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e, \u003cb\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d \u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d \u003cb\u003ei\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e子任务 4\u003c/b\u003e (30 分) : \u003cb\u003e2\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e3 × 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e, \u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d \u003cb\u003ei\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e子任务 5\u003c/b\u003e (30 分) : 原始约束\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/p\u003e\n\n\u003ch3\u003e示例\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n\u003ctt\u003e5\r\n1 4 3 2 5\r\n0 1 3 0 0\r\n1 2 3 4 5\u003c/tt\u003e\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n\u003ctt\u003e10\u003c/tt\u003e\r\n\r\n\u003c/pre\u003e\n\u003ch3\u003e解释\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003e示例 1.\u003c/b\u003e 从第一座山跳到第4座山,然后跳到第5座山;答案将是 0 + 0 + 0 + (4-1)^2 + (5-4)^2 \u003d 10\u003c/p\u003e"}}]}