ZJU/ZOJ 1499 Increasing Sequences 解题报告

题目大意是给出一个序列，要求将其分割，使在满足后面的数比前面的数大的基础上，最后一个数尽可能小，第一个数尽可能大，若存在多种分割方案则进而比较下一个数的大小，下一个数大的优先。

可以采用两次DP的方法，第一次求出最后一个数的最小值，第二次则反推第一个数的最大值。第一次的状态转移方程是f[i]=min(s[j..i])(f[i]>f[j-1]);第二次的状态转移方程是f[i]=max(s[i..j])(f[j+1]>f[i]);第一次DP时f[i]表示以第i位为序列终结，最后一个数的最小值。第二次DP时f[i]表示以第i位为当前所划分数的第一个数字，该数的最大值。在第二次DP时记录下状态转移的过程，则可顺推出输出序列。需要特别注意的是题目中允许前导0的规则，第二次DP时需要做一点特殊处理。

1647224 2008-09-19 14:00:52 Accepted 1499 FPC 90 404 LZOI_Test