ZJU/ZOJ 1539 Lot 解题报告

题目大意是n个士兵站成一列，每次可以让奇数或偶数位的士兵出列，问要使剩下士兵为3的出列方案总共有多少种。

很明显的递推，f[i]=f[i shr 1]+f[i shr 1+i mod 2]，边界条件f[3]=1。不过由于实际询问的状态很稀疏，如果将全部状态都先预处理出来时间上会造成很大浪费。因此更加好的方法是存储检索频繁的底层状态，然后利用记忆化搜索来递归求出询问的状态。这样也可以很好地优化空间复杂度。

3016511 2008-08-01 14:20:20 Accepted 1539 FPC 00:00.00 400K IwfWcf@LZOI