Chrety

动态规划

C++(8) DOS(2) Python(2) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

全部文章 / 动态规划（共12篇）

洛谷P1523 旅行商简化版(DP)

题目： P1523 旅行商简化版解析可以看做是两个人同时从西往东走，经过不一样的点，走到最东头的方案数设\(f[i][j]\)表示一个人走到i，一个人走到j的最短距离（\(i<j\)）第\(j+1\)个位置，两个人都可能走，两种情况 \(f[i][j+1]=min\{f[i][...

DP

2019-10-17

0 569

P2704 [NOI2001]炮兵阵地 (状压DP)

题目： P2704 [NOI2001]炮兵阵地解析：和互不侵犯一样就是多了一格用\(f[i][j][k]\)表示第i行，上一行状态为\(j\)，上上行状态为\(k\)的最多的可以放的炮兵发现\(100\times 1024\times 1024\)开不下还是通过简单的搜索发现就算\...

状压DP DP

2019-10-11

0 669

loj#10172 涂抹果酱 (状压DP)

题目： #10172. 「一本通 5.4 练习 1」涂抹果酱解析：三进制的状压DP 经过简单的打表发现，在\(m=5\)时最多有\(48\)种合法状态然后就向二进制一样枚举当前状态和上一层的状态进行转移就好了由于第\(k\)行是给定的，所以转移时要特判一下第\(k\)行，并且注意下一\...

DP 状压DP

2019-10-10

0 608

BZOJ1799: [Ahoi2009]self 同类分布(数位DP)

题目： 1799: [Ahoi2009]self 同类分布解析：设\(f[pos][SumDigit][rem]\)为第\(pos\)位，各位数和为\(SumDigit\)，当前余数为\(rem\)的数的个数要求\(n\)可以被各位数整除，也就是\(n\%SumDigit==0\) 这个...

数位DP

2019-08-16

0 482

BZOJ3209: 花神的数论题(数位DP)

题目： 3209: 花神的数论题解析：二进制的数位DP 因为\([1,n]\)中每一个数对应的二进制数是唯一的，我们枚举\(1\)的个数\(k\)，计算有多少个数的二进制中有\(k\)个\(1\) 设\(n\)的二进制一共有\(num\)位，有\(sum[i]\)个数的二进制中有\(k\)...

数位DP

2019-08-15

0 566

BZOJ1040: [ZJOI2008]骑士(奇环树,DP)

题目： 1040: [ZJOI2008]骑士解析：假设骑士\(u\)讨厌骑士\(v\)，我们在\(u\)，\(v\)之间连一条边，这样我们就得到了一个奇环树（奇环森林），既然是一颗奇环树，我们就先考虑把环断开，设断开边边连接的两点是\(rt1\)，\(rt2\)，断环的话直接标记这条边不能...

DP 图论奇环树

2019-08-15

0 494

BZOJ1864: [ZJOI2006]三色二叉树(树形DP)

题目： 1864: [Zjoi2006]三色二叉树解析：用\(f[u][0/1/2]\)表示以\(u\)为根，颜色为绿/红/蓝时最多的数量转移没啥好说的 \(f[u][0] = max(f[l][1] + f[r][2], f[l][2] + f[r][1]) + 1\) \(f[u][...

DP 树形DP

2019-08-14

0 536

BZOJ1003: [ZJOI2006]物流运输(最短路+DP)

题目： 1003: [ZJOI2006]物流运输解析：最短路+DP 我们用\(no[i][j]\)来表示\(i\)在第\(j\)天不可以经过用\(cost[i][j]\)表示第\(i\)天到第\(j\)天的花费在最短路的时候判断一下在第\(i\)天到第\(j\)天中哪些码头不可以走，在...

图论 DP 最短路

2019-08-13

0 565

树形DP求树的直径

思路：非常套路性的一个东西，记录一下，防止遗忘设\(f[i]\)表示以\(i\)为根，到其子树的叶节点的最大距离。考虑如何用子节点更新父节点，当前点到叶节点的最大距离=max{子节点到叶节点的距离+当前点到子节点的距离}。设\(u\)为当前节点，\(v\)为\(u\)的子节点，\(d...

DP 套路

2019-07-17

0 646

HDU2476 String painter(DP)

题目 String painter 给出两个字符串s1,s2。对于每次操作可以将 s1 串中的任意一个子段变成另一个字符。问最少需要多少步操作能将s1串变为s2串。解析太妙了这个题，mark一下。这个题先考虑怎么由空串转化s2， \(f[i][j]\)表示从空串到s2最少的次数，则有...

DP

2019-07-15

0 697