Codeforces Beta Round #14 (Div. 2) E. Camels 题解

4年前更新

1770

思路

四维dp。设 $f[i][j][k][0/1]$ 为第 $i$ 个点高度为 $j$ ，属于第 $k$ 个驼峰（包含上升段和下降段，峰属于上升段，谷属于下降段）， $0$ 代表位于上升段， $1$ 代表位于下降段。

显然状态转移方程为

f[i][j][k][0]=\sum\limits_{r=j+1}^4f[i-1][r][k][0]+f[i-1][r][k][1]\\ f[i][j][k][1]=\sum\limits_{r=1}^{j-1}f[i-1][r][k][1]+f[i-1][r][k-1][0]

© 版权声明

文章版权归作者所有，未经允许请勿转载。

THE END

喜欢就支持一下吧

相关推荐