# 2022-02-12 Test

real: 40 + 20 + 0

expect: 40 + 20 + 0

need: 100 + 20 + 0

links

sol

# 简

从大到小排序

设 $dp_{i,j,k}$ 表示选到第 $i$ 个元素，前面还有 $j$ 个元素未匹配，当前总和为 $k$ 的方案数

$a_i$ 第 $i$ 位权值

转移

$$dp_{i,j,k} = a\times dp_{i-1,j-1,k-a_i} + b\times dp_{i-1,j+1,k+a_i}+c\times dp_{i-1,j,k} + dp_{i-1,j,k}$$

分别表示这一位匹配与否，还有一个只由当前一个元素组成的集合。

考虑系数

$$a=1 \ \ \ \ 直接插一个坑 \\ b=j+1 \ \ \ \ 选一个坑填 \\ c=j \ \ \ \ 可以放进任意一个坑中$$

$$\mathrm O(n^3 v)$$

我是大傻逼

加个差分后，我们就不用管减法了，然后最大值就变成了 $k$ ，即可 $\color{green}\texttt{Accepted}$ 。

当然还有一些小细节，比如说差分数组每个坑都要连续变化，所以会有一个 $j\times a_i$ 之类的东西出现

然后 $\color{red}\texttt{z}\color{black}\texttt{xyhymzg}$ 就 $\mathrm O(n^3 v)$ 卡过去了 orz

# 单

考虑一张无向图，任意定向后最多的入度不为 $0$ 的点，它是等于无向图点数 $n$ 减去形成的树的个数 $v$ ，考虑对于一棵树，我们可将其定向为外向树，这样就只有一个入度为 $0$ 的点，而对于一个联通块，我们可以取出一棵基环生成树，将其定向即可实现没有一个入度为 $0$ 的点，这个定理得证。

然后我们要求最小的树的个数，可以转化为 $n$ 减去最多的定向后入度不为 $0$ 的点，然后对于一个集合内连边，我们可以看成给这个集合某一个点入度加 $1$ ，那把 $m$ 集合放一边，$n$ 个点放一边，从集合到属于它的每个点连边，这个二分图的最大匹配就是我们最多的定向后入度不为 $0$ 的点。

# 题

把平面图转成对偶图，相邻面之间从左向右连边，其最长链就是答案。

为什么，我也不知道

怎么写，我也不知道