CF1784D Wooden Spoon

这类问题通常可以按两种顺序 dp，本题中我们需要限制每组中最小的数依次递减，一种显然的想法是从大到小 dp，对于每个数考虑该数是与之前的某些数构成一组还是不做任何操作，类似于 ARC093F，当然由于我们需要对第一个数的每种取值计算方案数，所以 dp 需要反向，转移过程中的组合系数可能会很反常。另一种是从后向前，从小到大 dp，在填数的过程中留下一些空位，在后期对每个数决策是去填上之前的空位还是新开一组。两种方法都是 $O(n2^n)$ 的。

Read More

CF808G Anthem of Berland

数据范围明示 dp。首先在模式串上跑 kmp，预处理失配指针，dp 时遇到问号就暴力枚举字符集中每个字母，复杂度为 $O(|\Sigma|\cdot|S|\cdot|T|)$，可以卡过。

Read More

Description

有 $n$ 个结点，每个结点有两种状态：active 和 acquired。

一个 active 结点后面跟着若干 acquired 结点。

对于两个 active 结点 $A,B$，如果 $A$ 收购 $B$，那么所有跟着 $B$ 的结点变为 active，$B$ 变为 acquired 并跟在 $A$ 后面。

每次随机选择两个 active 结点，随机让其中一个收购另一个。

求只剩一个 active 结点的期望步数。

$n\le 500$

Read More

Description

$n$ 位选手参加比赛，共有 $m$ 套题，每套题包含 $p$ 个题目，第 $i$ 位选手答对第 $j$ 套题中第 $k$ 道的概率为 $f_{i,j,k}$。

每位选手选择一套题按顺序依次作答。若一位选手答对第 $i$ 题，会额外得到 $c_i$ 元奖励，注意每位选手只有答对了上一道题才会继续作答。

有 $y$ 条形如「第 $i$ 位选手的套题编号必须至少比第 $j$ 位的大 $k$」的限制。

给每一位选手分配一套题（不同选手可以相同），使所有人的期望奖励和最小，你需要求出这个最小值。

$1\le n,m,p\le 80,0\le y\le 10^3$

Read More

Catalan 数

Catalan 数表示为 $C_n$，有通项 $C_n=\dfrac{\binom{2n}{n}}{n+1}$ 和递推式 $C_n=\sum_{i=1}^nC_{i-1}C_{n-i}$，定义应该使用的是递推式。

Read More