作业帮 > 数学 > 作业

NOIP1999提高组第一题导弹拦截问题第二问标答的算法证明

来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/11/19 02:51:21
NOIP1999提高组第一题导弹拦截问题第二问标答的算法证明
NOIP1999提高组第一题导弹拦截问题第二问标答的算法证明
第二问朴素的是“潜力法”.就是用打的最低的炮台去打这个导弹.
更好的算法是求出所有下降序列的个数,即求最长上升序列.因为dilworth定理.
dilworth定理:最长的上升子序列每一个成员必不属于同一个下降子序列.
证明:设最长不降子序列中元素 ai,aj (i