动态规划100题（2/100）
副标题：继 NOIP2021 T2 没切掉内心无奈的愤怒之举。
1 [USACO2.3]奶牛家谱 Cow Pedigrees
背包+排列组合。
一个很明显的思路：令 \(dp_{i,j,k}\) 为当前为第 \(i\) 层，一共排了 \(j\) 个点，第 \(i\) 层排了 \(k\) 个点的方案总数。
显然，\(dp_{i,j,k}=\sum_{u=k/2}^{j-k}dp_{i-1,j-k,u}\binom {u} {k/2}\)。
主要是有两点：
1.此题我选择的不是上面那种打法，而是 \(dp[i+1][...][...]+=dp[i][j][k]\) 的打法，有些时候这种转移会方便一些。
2.乍一看 时间复杂度：\(\mathcal O({kn^3})\)，但常数比较可观，这也算一个 trick 吧。（事实上，NOIP2021 T2 的部分分打法用了这样的 trick）
#include
#include
#include
#include
#define LL long long
using namespace std;
const int Mod = 9901, MAXN = 205;
int dp[MAXN][MAXN][MAXN], n, k, jc[MAXN], inv[MAXN];
// 背包+排列组合
// dp[i+1][k]+=dp[i][j] (k%2==0&&k<=2j)
int Qpow(int x, int y) {
int ans = 1;
for(; y; y >>= 1) {
if(y & 1) ans = ans * x % Mod;
x = x * x % Mod;
}
return ans;
}
int C(int x, int y) {
if(x < 0 || y < 0 || x < y) return 0;
return jc[x] * inv[y] % Mod * inv[x - y] % Mod;
}
int main() {
int ans = 0;
scanf("%d%d", &n, &k); dp[1][1][1] = 1; jc[0] = 1;
for(int i = 1; i <= n; i ++) jc[i] = jc[i - 1] * i % Mod;
inv[n] = Qpow(jc[n], Mod - 2);
for(int i = n - 1; i >= 0; i --) inv[i] = inv[i + 1] * (i + 1) % Mod;
for(int i = 2; i <= k; i ++) { // 乍一看 kn^3，但/2/2/2常数小，这也算一个 trick 吧
for(int j = 1; j <= n; j ++) {
for(int u = 1; u <= j; u ++) {
for(int v = 2; v <= 2 * u; v += 2) {
if(j + v <= n) dp[i][j + v][v] = (dp[i][j + v][v] + dp[i - 1][j][u] * C(u, v / 2)) % Mod;
}
}
}
}
for(int u = 0; u <= n; u ++) ans = (ans + dp[k][n][u]) % Mod;
printf("%d", ans);
return 0;
}
2 CF840C On the Bench
插入 dp/dp+排列组合。