HDU 5623 KK's Number

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5623

题目翻译

http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=669&pid=1004

题解

( F \left [ x \right] ) 表示当前先手取到数字( x )为止所能达到的最大数字差。
明显,( F \left [ i \right ] = max \left { i – F \left[ j \right ] \right } , \left ( i > j \right ) )
但是这样会超时。
我们可以从小到大DP,这样就是( O \left( n \right) )的了。
( F \left [ i \right] = i – preMax )
( preMax = max \left ( preMax , F \left [ i \right ] \right ) )

代码