# 2022-02-12 Test

real: 40 + 20 + 0

expect: 40 + 20 + 0

need: 100 + 20 + 0

links

sol

#

从大到小排序

dpi,j,kdp_{i,j,k} 表示选到第 ii 个元素,前面还有 jj 个元素未匹配,当前总和为 kk 的方案数

aia_iii 位权值

转移

dpi,j,k=a×dpi1,j1,kai+b×dpi1,j+1,k+ai+c×dpi1,j,k+dpi1,j,kdp_{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可以放进任意一个坑中a=1 \ \ \ \ 直接插一个坑 \\ b=j+1 \ \ \ \ 选一个坑填 \\ c=j \ \ \ \ 可以放进任意一个坑中

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

我是大傻逼

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

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

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

#

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

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

#

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

为什么,我也不知道

怎么写,我也不知道

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝