分类:DP

[状压DP|AC自动机]bzoj1195: [HNOI2006]最短母串


<h3>题目描述</h3> 给定n个字符串(S1,S2,„,Sn),要求找到一个最短的字符串T,使得这n个字符串(S1,S2,„,Sn)都是T的子串。 <h3>输入</h3> 第一行是一个正整数n(n<=12),表示给定的字[......]

[AC自动机+DP]bzoj1030: [JSOI2007]文本生成器


<h3>题目描述</h3>   JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇[......]

[树形DP]loj2485:[CEOI2017]Chase


<h3>题目描述</h3> 在逃亡者的面前有一个迷宫,这个迷宫由 $n$ 个房间和 $n−1$ 条双向走廊构成,每条走廊会链接不同的两个房间,所有的房间都可以通过走廊互相到达。换句话说,这是一棵树。 逃亡者会选择一[......]

[DP]bzoj2298: [HAOI2011]problem a


<h3>题目描述</h3> 一次考试共有$n$个人参加,第$i$个人说:“有$a_i$个人分数比我高,$b_i$个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数) <h3>输入</h3> 第一行一个整数$n$,接下来$[......]

[数位DP]CF55D:Beautiful numbers


<h3>题目大意</h3> 求$L$到$R$中,能被每个非零位上的数整除的数字的个数。 $L,R\le9*10^{18}$ <h3>题解</h3> 数位DP; 首先,我们都知道一个数模$k$个数得到的数的种数为这$k$个树的$[......]

[DP]bzoj4806: 炮


<h3>题目描述</h3> 众所周知,双炮叠叠将是中国象棋中很厉害的一招必杀技。炮吃子时必须隔一个棋子跳吃,即俗称"炮打隔子"。 炮跟炮显然不能在一起打起来,于是rly一天借来了许多许多的炮在棋盘上摆了起来……他想[......]