OceanEye's Blog

很多人即使只见过一面,已经算见过了最后一面。

@OceanEye7年前

07/13
14:46
OI

BZOJ4361

神奇树状数组优化DP+组合数
思路很暴力……但是就是比较难连起来

第一步:
dp[i][j]表示枚举到第i位结尾且以第i位为结尾时 不下降子序列长度为j的情况数量

\( dp[i][j]=\sum_{k=1}^{j}(dp[i-1][k]) \)

第二步:
令 g[x] 表示所有长度为x的 不下降子序列 的数量

\( g[x]=\sum_{k=1}^{n}dp[k][x] \)

可以发现我们的ans和这个g[x]是由联系的
长度为x的 不下降子序列 的数量……和两个东西有关系

第一类—->从g[x+1]直接减少一位过来 第二类—->从非g[x+1]的过来 【参照定义理解】
第二类的数量是要记入答案的数量的
就稍微的暴力用n阶乘来做就好了,反正n不大

\( ans=\sum_{k=1}^{n}g[k]*(n-k)!-g[k+1]*g[k+1]*(n-k-1)!*(k+1) \)

以下代码

 

BZOJ4361