男人八题

Posted on By 二价氢

地址

###Task A Connected Graph

####题目大意:

求N个点的有向无环图的个数

####做法:

分治

如上图,将图分为两个联通块,两个联通块内只要有一条边是通的,这个图就是联通图,而这两个联通块内有个连边方案,减去不联通的一个即可

最后DP就能过

AC Code

###Task B

####题目大意:

合并石子

####做法:

第一眼:这不是水DP么?

第二眼:我去这数据范围能做?

有一种叫做“GarsiaWachs”的算法可以搞定这道题

AC Code

###Tack C

####题目大意:

类似于Betsy的旅行那一题,这回有禁止走的点

####做法:

#####做法1:

搜索加剪枝,超时无疑问

#####做法2:

状态压缩的插头DP,详见CDQ的《基于连通性状态压缩的动态规划问题》

AC Code

###Task D

####题目大意:

取石子游戏

####做法:

直接手推能推出规律

AC Code

###Task E

####题目大意:

求树上距离不大于的点对个数

####做法:

树的点分治,每次找树的重心为根进行搜索

显然有两种情况 一、两个结点不越过根,在根的子结点内讨论 二、两个结点越过根,根据距离直接讨论

这样就变成了Tree-DP问题

AC Code

###Task F

####题目大意:

多重背包问题

####做法

普通多重背包+优化

AC Code

###Task G

###Task H