秃头小白

dp

01背包(1) bfs(4) dfs(6) dfs序讲解(1) Dijkstra算法优先队列优化(2) KMP(1) LCA(4) STL(1) 二分(5) 二分图(3) 二进制(1) 二进制枚举(3) 优先队列(1) 倍增(2) 分治(2) 前缀和与差分(3) 区间dp(11) 博弈论(1) 图(1) 并查集(5) 快速幂(1) 思维题(55) 数学题(7) 数论(2) 整除分块（数论）(1) 最小生成树(2) 有关约数（质因数等）的基础数论(2) 栈(1) 树吧(5) 树状dp(1) 树状数组(2) 树状数组+dfs序(2) 模拟(4) 滑动窗口(4) 状压dp(1) 离散化+并查集(1) 离散化讲解及入门例题(2) 签到题(2) 素数筛(1) 线段树(10) 贪心(12) 逆元(1) 逆序对的三种求法(1) 题解(16) 高精度(8)

/ 注册

全部文章 / dp （共7篇）

CodeForces - 1461B B - Find the Spruce 来自专栏

题目链接 https://vjudge.net/contest/413174#problem/B 解题思路 dp。dp[i][j]表示以点(i,j)为树顶的树的个数，最后求一下所有位置的点为树顶能构成的树的个数之和，即为答案。转移方程：开始所有为 * 的位置全部初始化为1，dp[i][j]+=min...

2020-12-13

1 780

CF666A Reberland Linguistics 来自专栏

题目链接 https://www.luogu.com.cn/problem/CF666A 解题思路居然是dp。提醒：twice in a row译为连续两次dp[i][2]=1表示(i,i+1)满足条件，=0表示不满足；dp[i][3]=1表示(i,i+1,i+2)满足条件，=0表示不满足。转移...

2020-12-13

1 758

小游戏来自专栏

题目链接 https://ac.nowcoder.com/acm/contest/9667/J 解题思路一开始还以为选奇数或偶数权值最大的就行嘞，结果发现是错的，比如1，4，可以两个都选，并不是只能选奇数或者偶数。简单dp；dp[i][1/0]表示第i个数选还是不选；但是这里的第i个数并不是a数组...

2020-12-08

0 753

Bang! Bang! 来自专栏

题目链接 https://ac.nowcoder.com/acm/contest/9715/C 解题思路找关系：总共m个重音符，除去最左边的重音符还剩m-1个，我们确定最左边重音符的位置，计算此时剩下的m-1个重音符的位置关系有多少种：假设m-1=1，最左边的重音符偏移了0位，即如下图：此时，...

2020-12-05

0 724

Strange Towers of Hanoi 来自专栏

题目链接 http://poj.org/problem?id=1958 解题思路三个的汉诺塔就不细说了，太基础了（还是细说了……）：将n个盘子从A通过B移到C的方案数表示为tir[n]，完成这件事就得先把前n-1个盘子从A通过C移到B，方案数为tir[n-1]；再把第n个盘子从A直接移动到C，方案...

2020-11-20

1 655

L3-2 至多删三个字符

题目（来自PTA，没有测试平台）给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3 个字符，结果可能有多少种不同的字符串？输入格式：输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 10^6] 内的字符串。输出格式：在一行中输出至多删掉其中 3 个字符后不同字符串的个数...

2020-10-25

2 815

祝（原题来自计蒜客染色（简单））

题目链接 https://vjudge.net/contest/397650#problem/Ahttps://nanti.jisuanke.com/t/48301 解题思路简单dp+简单贪心，甚至不能算贪心。S1：先用dp[i]存，在不算特殊区间的情况下，前i个位置染色的最大值；S2：对pos的...

2020-09-28

1 597