标签：排列 题目 部落 最大值 SDOI2010 P2467 可以
P2467 [SDOI2010]地精部落
题目大意：略
题目分析：
首先一眼可以知道这个是个计数类的问题，我们可以考虑使用组合数学和 \(dp\) ，由于题目让我们求奇数项都高于或低于偶数项的排列数，我们观察题目所让求的这种排列，发现将原来符合的排列倒过来之后仍然符合。然后我们可以考虑使用 \(dp\) ，我们令 \(f_i\) 为当前排列长度为 \(i\) 时的方案数，那么我们可以知道当前的排列可以有某些小的排列转化而来，那么显而易见，我们可以枚举有多少个数在最大值的左侧，那么整个区间就被封为了三段，我们可以知道最大值左右两侧的排列互不干扰，因为他们只对当前序列的离散后的排列产生影响，所以我们可以枚举最大值所在的位置，即最大值左侧有多少个元素，那么很明显转移方程已经可以得出了： \(f_i = f_{j - 1} * C_{i -1}^{j -1} * f_{i - j}\)。
标签：排列,
题目,
部落,
最大值,
SDOI2010,
P2467,
可以
From： https://www.cnblogs.com/L3067545513/p/16743117.html