洛谷P2831 愤怒的小鸟 + 篮球比赛1 2

这三道题一起做,有一点心得吧。

愤怒的小鸟,一眼看上去是爆搜,但是实现起来有困难(我打了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个算作在,然后前缀和处理。

但是还是要具体情况具体分析。

上一篇:【Xamarin 挖墙脚系列:Windows 10 一个包罗万象的系统平台】


下一篇:JUnit01Eclipse添加JUnite