HNOI/AHOI2018 道路
暴力 DP + 优化空间。
【记录】
ZJOI2007 时态同步
【记录】
NOI2002 贪吃的九头龙
首先判断无解。
然后对于小头数量 (ge2) 的情况，只有大头需要算树枝，这是因为两种颜色就可以对树进行独立染色。
于是设 (f(u,s,1/0)) 表示子树 u， 大头吃了 s 个果， u 是否被大头吃的。
转移时合并子树，方程为：
[f(u,s,k) = min_{0le tle s}Bigg[f(u,t,k) + min{f(v,s-t,koplus1),f(v,s-t,k)+[k=1mid m=2]W(u,v)}Bigg]
]
【记录】
POI2013 LUK-Triumphal arch
首先可以二分 k， 接下来解决判定性问题。
假设 1 为根。
可以发现，B 一定不会向 1 走。
设 (f(u)) 表示点 (u) 需要多染多少次才能让 (A) 胜利。
【记录】
SP3734 PERIODNI - Periodni
算法上，笛卡尔树秒天秒地；
实现上，原地卷积恐怖如斯
（bushi
SPOJ 上不去， luogu remote judge 上不去，vjudge 也崩，就贴个代码吧。
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int mo = 1e9 + 7, N = 503;
int ksm (int a, int b) {
int res = 1;
for (; b; b >>= 1, a = (LL)a * a % mo)
if (b & 1) res = (LL)res * a % mo;
return res;
}
int n, k, h[N];
int sta[N], tp, ls[N], rs[N];
int fac[1000003], ifac[1000003];
int C (int x, int y) {
if (y > x) return 0;
return (LL)fac[x] * ifac[y] % mo * ifac[x - y] % mo;
}
int f[N][N], siz[N];
void dfs (int x, int delt) {
f[x][0] = 1;
siz[x] = 1;
int Hight = h[x] - delt;
if (ls[x])
{
int y = ls[x];
dfs (y, h[x]);
for (int i = min (k, siz[x] + siz[y]); i >= 0; -- i)
for (int j = max (1, i - siz[x]); j <= siz[y] && j <= i; ++ j)
f[x][i] = (f[x][i] + (LL)f[y][j] * f[x][i - j] % mo) % mo;
siz[x] += siz[y];
}
if (rs[x])
{
int y = rs[x];
dfs (y, h[x]);
for (int i = min (k, siz[x] + siz[y]); i >= 0; -- i)
for (int j = max (1, i - siz[x]); j <= siz[y] && j <= i; ++ j)
f[x][i] = (f[x][i] + (LL)f[y][j] * f[x][i - j] % mo) % mo;
siz[x] += siz[y];
}
for (int i = min (k, siz[x]); i >= 0; -- i)
for (int j = 0; j < i && j < siz[x]; ++ j)
f[x][i] = (f[x][i] + (LL)f[x][j] * C (Hight, i - j) % mo * C (siz[x] - j, i - j) % mo) % mo;
}
int main()
{
fac[0] = 1;
for (int i = 1; i <= 1000000; ++ i)
fac[i] = (LL)i * fac[i - 1] % mo;
ifac[1000000] = ksm (fac[1000000], mo - 2);
for (int i = 1000000; i >= 1; -- i)
ifac[i - 1] = (LL)i * ifac[i] % mo;
scanf ("%d%d", & n, & k);
for (int i = 1; i <= n; ++ i) {
scanf ("%d", & h[i]);
while (tp && h[sta[tp]] > h[i]) ls[i] = sta[tp --];
if (tp) rs[sta[tp]] = i;
sta[++ tp] = i;
}
int root = sta[1];
dfs (root, 0);
cout << f[root][k];
return 0;
}