#BZOJ1925

BZOJ1925 [Sdoi2010]地精部落 动态规划

  给出n,n<=4200,问1~n这些数的排列中,有多少满足一下性质:  性质:对于一个数,满足它的相邻数都大于或者小于它。  答案modP  一道明摆着的动归题。  我们用dp[i][j]表示长度为i的序列(数字<=i),最终数为j的方案数。  我们只考虑开始的时候下降的情况,因为开始的时候上升的情况数...