动规虐我千百遍,我待动规.....咳咳。

T1

题目来源:未知
题目描述:用第 1 个、第 2 个…第 N 个斐波那契数构成一个长度为 P 的序列,每个斐波那契数可以使用任意多次,但至少要使用一次,并且序列中任意两个相同的斐波那契数之间至少要隔着 M 个数,pf 希望知道满足条件的序列组成方法有多少种。
解题思路:做了1个半小时没有结果的我感觉自己已经疯了,用容斥瞎搞了一通后发现居然很多数据都可以过,然后就没管了,然后就蜜汁A了?不是很明白,等彻底了解容斥后再说吧。
代码

T2

题目来源:codevs1997(bzoj上也有不过是权限题)
题目描述:略
解题思路:伪概率dp,因为最多只有200块地图残片,所以背包只要开到200就可以了,超额的统统变成200,然后用f[i][j][k]表示到第i场比赛为止赢了j场背包剩余容量为k的概率。正因为背包这个变,所以不能够用f[i][j][k]=f[i-1][j-1][k-a[i]]×p[i]+f[i-1][j][k]×(1.0-p[i])这个公式,而要正着推。具体看代码
代码

T3

题目来源:codeforces11D(多古老的题目了)
题目描述:求大小大于3的简单环个数
解题思路:状压dp,用f[i][zt]表示经过的点集为zt时,以i为终点可以获得的环的数量,初始化f[i][(1<<i)]=1,因为如果要求这样一个状态,扩展出来的肯定有环。
然后做一个简化,每次从比当前起点编号大一些的点开始枚举,比如说有一个简单环1-2-3-1,也会被枚举1-3-2-1,所以最后得到的答案要除以2
显然对于每一个与i联通的点j,有代码中的递推式。不过如果j已经包含在zt集合中就不用算了,以后会算一个新环的。
代码:

T4

题目来源:洛谷P2627,codevs4654(bzoj上又是权限题)
题目描述:略
解题思路:用f[i]表示删掉第i头牛使得满足条件的最小去掉牛的价值和,然后用单调队列优化dp
代码