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

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

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

BZOJ2510 弱题 循环矩阵+DP

DP方程很裸,$$f_{i}=\frac{1}{m}*f_{i-1}+\frac{m-1}{m}*f_{i}$$,但是数据范围告诉我们裸的DP过不去,甚至连O(n^3logk)也过不去。仔细观察,这是一个循环矩阵,每一行都是第一行移位得到的,即Bi,j=Bi+1,j+1。因此,可以利用这个性质,只保···
BZOJ4870 [Shoi2017]组合数问题 矩阵快速幂优化DP 动态规划

BZOJ4870 [Shoi2017]组合数问题 矩阵快速幂优化DP

本省的省选题,考虑所求式子的实际含义。分析可知,原式等价于“在n*k个物品中,选出物品数余数为r的方案数”,可以DP求出来。 设f[i][j]:前i个物品,选出物品数余数为j的方案总数,f[i][j]=f[i-1][j](第i个未选)+f[i-1][(j-1+k)%k](第i个选了)。 但是,由于n···
BZOJ1030 文本生成器 && POJ2778 DNA Sequence  AC自动机 字符串

BZOJ1030 文本生成器 && POJ2778 DNA Sequence AC自动机

先上题目:   这俩题非常相似,给出文本串的长度和一些目标串,求所有经过/不经过单词节点的串的数量。 第一道题给的目标串数目多,而且比较长,所以在Trie树中节点数较多,而文本串长度较小,所以可以采用DP的思路搞出来:设f[i][j]:走了i步,当前在自动机上j号点时的方案总数。构建出tr···