动态规划专题(1)
例题26 约瑟夫环的变形(And Then There Was One, Japan 2007, LA 3882, POJ 3517)
经典问题,递推解决
1 |
|
例题27 王子和公主(Prince and Princess, Uva 10635)
LCS问题,可转为LIS问题
1 |
|
例题28 Sum游戏(Game of Sum, Uva 10891)
动态规划,用dp[i][j]表示第i~j个元素组成的子元素先手能拿的最大分,则后手能拿的最大分就是sum[i][j]-dp[i][j]
1 |
|
例题29 黑客的攻击(Hackers’ Crackdown, Uva 11825)
状态dp,用二进制表示状态。通过这题学习到原来枚举集合S的子集的一个好方法,详看代码
1 |
|