【dp专题002】hdu 4489 The King’s Ups and Downs (dp)

题目链接

题意:问长度为n的“波浪”型排列(即1..n每个数出现一次)有多少。波浪型的含义是,“高低高”或者“低高低”

思路:我们考虑当前已经知道i-1个数的波浪型的排列的方案数,那么当第i个数到来时,第i个数一定是最大的。

那么将i插入到某个位置,必须满足该位置前面必须以“高低”结尾,该位置后面必须以“低高”结尾才合法。(特别地,允许前面或者后面为空,这点体现在初始化上)

因此我们分别考虑,用dp[i][0]表示有i位且最后结尾为“高低”的方案数,dp[i][1]表示有i位且最后结尾为“低高”的方案数。

此时我们的情况是,已经有i-1个数,我要把第i个数插在某个位置。

这个位置是不确定的,因为我们需要枚举插入的位置(表现为,枚举插入的第i个数前面有j个数,后面剩余i-1-j个数)

那么第i个数前面是选择哪j个数呢? 组合数为C[i-1][j] (i-1个数选择j个放在前面)

因此长度为i的答案为sum[i] = sigma{dp[j][0]*dp[i-j-1][1]*C[i-1][j]} (0=<j<i)

dp[i][0]和dp[i][1]对称,显然相等,都等于sum[i]/2.

我们只需要再预处理一个组合数就好了。

 

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz