HBC232732[JSOI2008]球形空间产生器SPHERE,高斯消元,线性代数禅题解（你是一个骑士吗？）

把回忆走一遍算法基础篇 2023-11-09 15:20:02 53 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

只是我手上的傀儡而已，冲锋！本题请格外注意标红和加粗的字！你的任务目标是营救被困于该格的公主，你需要选择一个公主不在的格子作为起点，任意时刻不重复经过已经走过的点，到达某个格子时，必须与当前怪物战斗，如果战斗力严格大于其战斗力，可以击败它并获得它所具有的全部战斗力，使得能完成任务目标。

骑士？只是我手上的傀儡而已，冲锋！本题请格外注意标红和加粗的字！你是一个骑士，现有一个包含 N N 个格子的一维棋盘（一行 N N 列）。第 i i 个格子有一个战斗力为 a_i a i 的怪物：所有怪物对应的 a_i>0 a i >0，若 a_i=0 a i =0 表示第 i i 列是公主。你的任务目标是营救被困于该格的公主（走到公主所在的格子），你需要选择一个公主不在的格子作为起点，任意时刻不重复经过已经走过的点。到达某个格子时，必须与当前怪物战斗，如果战斗力严格大于其战斗力，可以击败它并获得它所具有的全部战斗力。形式化地，设你的战斗力是 m m，怪物的战斗力是 a_i a i ： text{战斗}begin{cases}mle a_irightarrowtext{任务失败}\m> a_irightarrowtext{击败该怪物，且}~mleftarrow m+a_iend{cases} 战斗{ m≤a i →任务失败 m>a i →击败该怪物，且 m←m+a i 给定序列 {a_n} {a n }，求采用最优策略选择起点及行动路径时最少的初始战斗力 m_0 m 使得能完成任务目标。