过时往事

文章
7
资源
0
加入时间
2年10月21天

hdu2604 queuing(dp+矩阵倍增)

f[i]表示i个人排队时为E-queue的方案数。则有:f[n]=f[n-1]+f[n-3]+f[n-4] 解释一下:第n个人为m时,前n-1个只要合法就行,所以是f[n-1]. 第n个人为f时,前n-1个人合法不能保证这n个都合法,我们再看第n-1位,第n-1位为m时,第n-2为显然只能是m,这样的话只要保证前n-3个合法即可,所以是f[n-3]。第n-1位为f时,第n-2为显然只能是m,第n