BZOJ4000 [TJOI2015]棋盘 状压DP+矩阵乘优化 动态规划

BZOJ4000 [TJOI2015]棋盘 状压DP+矩阵乘优化

题目描述不是很清楚,实际上就是给你一个矩阵表示每个点的攻击范围,若下标均从1开始,点在第2行第p+1列,求放棋子的可行方案。 实际上是状压DP的水题,枚举行,枚举上一行状态,枚举本行状态即可,但是这题的行数开的比较大,实测普通的DP只能得70分,观察式子发现,合法的状态并不多,每行撑死也就64种,而···