信息学奥赛一本通 1322：【例6.4】拦截导弹问题(Noip1999)

证明：存在最优解包含第一次的贪心选择，也就是说最大值$g$是某个数字序列的第一个数字。

假设所有的最优解都中$g$都不是第一个数字，
某最优解中，存在子序列$a_1,a_2,...,g,...,a_m$，由于该子序列为不升子序列，那么$a_1\le a_2\le ...\le g$，而$g$是所有数字中的最大值，因而有$g\ge a_1$，所以$a_1=g$，该序列的第一个数字就是$g$，与假设相悖，原命题得证。

证明：假设前k次都进行贪心选择，存在最优解包含第k+1次的贪心选择$g$。
1） 如果$g$是某子序列的第一个数

假设所有的最优解都不包含第一个数是$g$的子序列，任选一个最优解，存在在第k次选择后选择到的数字构成的子序列$a_1,a_2,...,g,...,a_m$，由于该子序列为不升子序列，那么$a_1\ge a_2\ge ...\ge g$，而$g$是第k次选择后选择的数字中的最大值，因而有$g\ge a_1$，所以$a_1=g$，该序列的第一个数字就是$g$，与假设相悖，原命题得证。

2）如果$g$不是某子序列的第一个数
也就是说，存在子序列$a_x,a_{x+1},...,a_k$，$a_k$是第k次的贪心选择，前k次的贪心选择已经固定。下一次贪心选择是$g$，应该与$a_k$在同一序列且在$a_k$的后面。

假设所有最优解中不存在$a_k$在子序列中的下一个数字是$g$的情况。
1.如果$a_k$与$g$仍然在同一子序列，那么有：$a_x,...,a_k,a_{k+1},...,g,...,a_m$
已知g是第k次贪心选择后选择的数字中的最大数字，那么有$g\ge a_{k+1}$，因为这是不升序列，那么有$a_{k+1}\ge g$，所以$a_{k+1}=g$，$a_k$的下一个数字是$g$，与假设相悖。
2.如果$a_k$与$g$不在同一子序列中，
$g$不可能接在由前k次贪心选择构成的老序列的后面。如果能接在老序列的后面，之前做贪心选择时就会选到$g$。
因而$g$所在的序列一定是由第k次贪心选择之后选择到的数字组成的，可能为：$a_y,a_{y+1},...,a_{g-1},g,a_{g+1},...,a_{ge}$。这是不升序列，所以$a_y\ge g$
由于$g$是第k次贪心选择后剩余数字中的最大数字，所以$a_y\le g$，所以有$a_y=g$。
因此g一定是某个序列中的第一个数字，该序列为：$g,a_{g-1},g,a_{g+1},...,a_{ge}$
第k次贪心选择$a_k$存在的序列为$a_x,a_{x+1},...,a_k,a_{k+1},...,a_m$(也可能不存在$a_{k+1},...,a_m$)，
由于$g\le a_k$，序列$a_x,a_{x+1},...,a_k,g,a_{g+1},...,a_{ge}$一定也是不升序列。
如果$a_{k+1},...,a_m$不存在，则将$g$所在的序列接在$a_k$的后面，构成序列$a_x,a_{x+1},...,a_k,g,a_{g+1},...,a_{ge}$，总序列数量减少，仍然是最优解。
如果存在$a_{k+1},...,a_m$，那么将序列$g,a_{g+1},...,a_{ge}$与$a_{k+1},...,a_m$交换。得到序列$a_x,a_{x+1},...,a_k,g,a_{g+1},...,a_{ge}$与$a_{k+1},...,a_m$，总序列数量不变，仍是最优解。
无论何总情况，总能构造出满足$a_k$在子序列中下一个数字是$g$的最优解。与假设相悖，假设不成立，原命题得证。