Chrety

分类

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

/ 注册

全部文章（共11篇）

P1108 低价购买 (DP)

题目 P1108 低价购买解析这题做的我身心俱惫，差点自闭。当我WA了N发后，终于明白了这句话的意思当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。这题有两问，第一问显然最长严格下降子序列，一看数据范围：5000，跟最长严格上...

DP

2019-05-24

0 629

P1018 乘积最大(DP)

题目 P1018 乘积最大解析区间DP 设\(f[i][j]\)表示选\(i\)个数，插入\(j\)个乘号时的最大值设\(num[i][j]\)是\(s[i,j]\)里的数字转移方程就是\(f[i][k] = max(f[i][k], f[j][k - 1] * num[j + 1][...

DP

2019-07-13

0 435

解题报告

author：sdgzy 6.12日 T1总感觉是一个假题，T3推推式子看出单调性就没了。 T2比较有意思：题目大意：n个物品，属性为w,r，选择第i件物品后，之后每选择一个物品都会减去r的价值。求按顺序选择物品的最大价值。 solution：考虑对于一个必须选择的物品集合（...

DP

2019-06-12

0 416

HDU2476 String painter(DP)

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

DP

2019-07-15

0 697

树形DP求树的直径

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

DP 套路

2019-07-17

0 646

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

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

图论 DP 最短路

2019-08-13

0 565

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

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

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

DP 图论奇环树

2019-08-15

0 494

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

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

DP 状压DP

2019-10-10

0 608

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

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

状压DP DP

2019-10-11

0 669