Category Archives: 动态规划

CodeForces 735E Ostap and Tree (树形dp)

给出一棵树,开始时树的每个节点都是白色,将树某些点染成黑色使得任何一个点都存在一个黑色点距离他不超过k。 问题 …

Codeforces Gym 101147F Bishops Alliance (dp,BIT)

n * n的各自上有m个西方象棋的象,每个象定义x, y, p,求最大的一组象,他们在同一个对角线并且任意两个 …

HDU 5121 Just A Mistake (树形dp,组合数)

给出一颗树,按照某个顶点序号的排列,按照顺序将点加入集合(于集合内点没有变),这样每种排列会构造出一种独立集, …

HDU 4916 Count on the path (树形dp,恶心分类讨论)

给出一棵树,计算整棵树中不在u~v路径中的点编号的最小值。 需要维护dp[u][0]表示以u位根的子树 min …

HDU 5977 Garden of Eden (树形dp)

树上每个点有一种颜色,最多k种(k <= 10,现在赛是7,当然这个不重要,我写题解只是想写一种完爆标程 …

CodeForces 477D Dreamoon and Binary (dp,后缀数组)

给出一个目标二进制串,初始是n=0(十进制),有两种操作:1.n = n + 1;2.在之前输出的二进制串末尾 …

CodeForces 480E Parking Lot (线段树,dp)

一个N * M的矩阵,里面有.和X,给出若干询问,询问将(x, y)位置变成X,求剩下部分的矩阵由.构成的最大 …

HDU 4117 GRE Words (AC自动机,dp,线段树)

给出n个字符串,以及格子的权值,按照顺序取出若干个字符串,要去前一个字符串是后一个字符串的子串。计算最大权值和 …

UVALive 6495 (AC自动机,高斯消元)

一个硬币,正面用T表示反面用H表示,现在两个人各自猜了一个长度是L的序列,序列每个元素表示正面还是反面,现在硬 …

HDU 4433 locker (dp,贪心)

给出n长度的密码锁,密码锁可以通过拇指波动,但是拇指同时最多能波动3格密码锁,求从初始密码锁状态变到目标密码锁 …