「CEOI2016」袋鼠
statement
一行共有 \(N\) 个格子，从左到右从 \(1\) 到 \(N\) 编号。一只袋鼠从 \(c_s\) 出发，经过恰好 \(N - 1\) 次跳跃，到达 \(c_f\) ，并且经过所有的 \(N\) 个格子，每次跳跃的方向都与上一次不同。如果袋鼠当前所在的格子为 \(\rm current\) ，来自 \(\rm prev\) ，则其下一个格子 \(\rm next\) 满足：
- 如果 \(\rm prev < current\)，则 \(\rm next < current\) ；
- 如果 \(\rm current < prev\)，则 \(\rm current < next\) 。
求不同的跳跃方案数除以 \(10 ^ 9 + 7\) 的余数。
Hints
\(2\le N\le 2000\)，\(c_s \neq c_f\) .
solution
线头 DP ...
其实就是一个求排列个数的问题，这里的排列指的就是跳跃的下标序列。
然后开始线头，设 \(f(i, j)\) 表示填了前 \(i\) 个数，产生 \(j\) 个没有接的向上的线头的方案数，转移：
其实这个转移方程就是接几个散乱的线头的过程。
对于 \(c_s\) 和 \(c_f\) ，默认它们的线头位于最左边和最右边，然后答案就是 \(dp(n - 1, 0)\) ，因为这个时候最后一个数字的摆放位置是唯一的。
考虑这个东西为什么可以不重不漏，因为在一个排列中，每个线头可以看成一个笛卡尔树，合并相当于两颗二叉树用根节点接牢，增加一个线头可以看成新建一个节点的笛卡尔树，而笛卡尔树的形态和一个排列可以构成双射，所以保证了每次的不同。
时间复杂度 \(\mathcal O (n^2)\) 。
int n, s, t, dp[N][N];
int main() {
scanf("%d%d%d", &n, &s, &t);
dp[0][0] = 1;
forn(i,1,n) forn(j,0,i) {
if(i != s && i != t) {
dp[i][j] = 1ll * dp[i - 1][j + 1] * (j + (i > s) + (i > t)) %Mod * (j + 1) %Mod;
if(j) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) %Mod;
} else {
dp[i][j] = dp[i - 1][j];
dp[i][j] = (dp[i][j] + 1ll * dp[i - 1][j + 1] * (j + 1) %Mod) %Mod;
}
}
printf("%d\n", dp[n - 1][0]);
return 0;
}
Thinks
使用这种解决排列问题的 DP 的充要条件。
这个模型的特点：
- 不重不漏
- 无后效性
而且这两个特点都是基于每个小集合的笛卡尔树，所以能使用这个东西的时候，序列中的数不一定是排列，但是要保证不同序列都只能对应一颗笛卡尔树，所以序列中的数字必须两两不同，并且枚举的时候从小到大或从大到小。
HDU6764 Blood Pressure Game
statement
给一个长度为 \(n\) 的数组 \(a\)，定义一个数组的权值为
求在 \(a\) 的每一种排列中，权值严格前 \(k\) 大方案的权值，以及每种方案的方案数，方案数对 \(10 ^ 9 + 7\) 取模。
Hints
\(n\le 600\) ，\(k\le 20\) , 数组 \(a\) 中整数大小互不相同 .
solution
套路地把贡献拆成排序后的数组 \(a\) ，数 \(|a_{i + 1} - a_i|\) 的个数。
由于元素互不相同，采用上述模型，设 \(dp(i, j, k)\) 表示从小到大加入了前面 \(i\) 个数，构成的集合个数为 \(j\) ，是否确定首尾的状态。
其中 \(k = 0\) 表示没有确定首或尾，\(k = 1\) 表示确定了首尾中的一个，\(k = 2\) 表示首尾全部确定了。
由于要记录前 \(k\) 大，所以每个状态除了计数，还要记录转移后序列的每一种权值的集合。
初始状态 \(dp(1, 1, 0)\) 和 \(dp(1, 1, 1)\) 。
首先是权值的转移，发现从 \(dp(i,,)\rightarrow dp(i + 1,,)\) 的贡献是相同的，都是 \((a_i - a_{i - 1}) \times (2j - k)\) 。
因为有 \(j - k\) 个集合需要连左边和右边，\(k\) 个集合只需要接一边，加之每次加入的都是比当前元素大的元素，这样的过程自动完成了一个差分的前缀和。
对于每种集合的构造，一定不能破坏上述的权值计算的过程，所以，确定为首尾的集合只能在一边进行构造，不能在另一边构造，这会影响到对于方案数转移的过程。
分类讨论方案数的转移：
- 新建一个集合，不作为首尾，\(dp(i + 1, j + 1, k)\leftarrow dp(i, j, k)\) ，方案数为 \(j - k + 1\) 。
- 新建一个集合，作为首尾，\(dp(i + 1, j + 1, k + 1)\leftarrow dp(i, j, k)\) ，方案数为 \(2 - k\) .
- 合并两个集合，\(dp(i + 1, j - 1, k)\leftarrow dp(i, j, k)\) ，因为求最大权值的特殊性，集合在序列中的排列顺序已经确定，方案数为 \(j - 1\) .
- 新建一个集合，并且在这一轮就与另一个集合合并，不作为最后的 \(a_1\) 或 \(a_n\) ，\(dp(i + 1, j, k)\leftarrow dp(i, j, k)\) ，方案数为 \(2j - k\) .
- 新建一个集合，并且在这一轮就作为 \(a_1\) 或 \(a_n\) ，与其他集合合并，\(dp(i + 1, j, k + 1) \leftarrow dp(i, j, k)\) ，方案数为 \(2 - k\) .
实现的时候，对于每种状态都记录前 \(k\) 最大权值的方案，每种方案记为二元组 \((val, num)\) ，分别为这种排列的权值以及对应的方案数。
对于每个状态记录的二元组对于关键字 \(val\) 先排序，记录前 \(k\) 个后，再进行转移。
时间复杂度 \(\mathcal O (n ^ 2 k\log k)\) 。
int n, m; i64 a[N];
struct state {
node U[M * 5]; int num;
state() {num = 0;}
inline void reset() {num = 0;}
inline void ins(i64 val, Mint t) {U[++num] = node(val, t);}
inline void init() {
sort(U + 1, U + num + 1);
int sem = 0;
forn(l,1,num) {
int r = l; Mint sum = U[l].num;
while(r < num && U[r + 1].val == U[l].val) sum += U[++r].num;
U[++sem] = node(U[l].val, sum);
l = r;
}
num = min(m, sem);
}
} dp[3][2][N];
inline void solve() {
scanf("%d%d", &n, &m);
forn(i,1,n) scanf("%lld", a + i);
sort(a + 1, a + n + 1);
dp[0][1][1].ins(0, Mint(1)), dp[1][1][1].ins(0, Mint(2));
int now = 1;
rep(i,1,n) {
forn(j,1,n) rep(k,0,3) if(dp[k][now][j].num) {
dp[k][now][j].init();
forn(t,1,dp[k][now][j].num) {
i64 val = dp[k][now][j].U[t].val + (a[i + 1] - a[i]) * (2 * j - k);
Mint num = dp[k][now][j].U[t].num;
if(j - k + 1 > 0) dp[k][now ^ 1][j + 1].ins(val, num * Mint(j - k + 1));
if(2 * j - k > 0) dp[k][now ^ 1][j].ins(val, num * Mint(2 * j - k));
if(j > 1) dp[k][now ^ 1][j - 1].ins(val, num * Mint(j - 1));
if(k < 2) {
dp[k + 1][now ^ 1][j].ins(val, num * Mint(2 - k));
dp[k + 1][now ^ 1][j + 1].ins(val, num * Mint(2 - k));
}
}
dp[k][now][j].reset();
}
now ^= 1;
}
dp[2][now][1].init();
forn(i,1,min(m, dp[2][now][1].num)) printf("%lld %d\n", dp[2][now][1].U[i].val, dp[2][now][1].U[i].num.res);
forn(i,1,m - dp[2][now][1].num) puts("-1");
forn(j,1,n) rep(k,0,3) if(dp[k][now][j].num) dp[k][now][j].reset();
}