这三道题一起做,有一点心得吧。
愤怒的小鸟,一眼看上去是爆搜,但是实现起来有困难(我打了0分出来)。
还有一种解法是状压DP。
抛物线一共只有那么多条,我们枚举抛物线(枚举两个点),这样就能够预处理出b[i][j]
表示过点i,j的抛物线经过的点(状压)。
然后写了个记忆化搜索,枚举每个状态是通过哪个抛物线转移而来(可能转移后比现状态经过的点要多,但是不影响答案正确性)
那么就这样A了...
论状态压缩的多种应用——篮球比赛2:
这题也是状压DP,但是DP的状态设计很NB:
f[i][sta]表示前i个人拼出状态sta的方案数。
然后不是枚举如何转移而来,而是从这个点向后转移,也就是所谓的刷表法。枚举当前状态下一个人的取值然后转移。
篮球比赛1:
f[i][j]表示前i个人 ^ 出数字j的方案数,往后转移。
g[i][j]表示后i个人 & 出数字j的方案数,往后转移。
真神了。。。
如何确定一道题要状态压缩?不确定...凭感觉啊!题做多了就好了吧。
主要是学习了这种形式的状态的刷表法。
其他的大多数状压DP基本上都能够记忆化搜索,不用自己想DP顺序。
还有,DP有两种方式:第i个在决策中 和不一定在。
貌似大部分都是把第i个算作在,然后前缀和处理。
但是还是要具体情况具体分析。