已注销

动态规划

ACM模版篇(139) C++(4) CONTESTS(31) dfs && bfs(59) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 区间(22) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

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

51Nod－1270－数组的最大代价

ACM模版描述题解动态规划，极端考虑法，每个A[i]要么取1，要么取B[i]。状态转移方程也很好推（dp[i][j]:j->0表示A[i]取1，j->1表示A[i]取B[i]）: dp[i][0] = max(dp[i - 1][0], dp[i - 1][1...

2021-05-21

0 594

51Nod－1086－背包问题 V2

ACM模版描述题解这里提供三种代码，前两种方法一致，复杂度O(V*Σlog n[i])，不同的是，第二个是模版；第三种代码最优，复杂度为O(VN)，可惜十分不好理解，具体推导过程不再赘述，有些懵懵懂懂…… 这个问题是一道常见的多重背包问题，和完全背包相似，可以转化为01背包问题，但...

2021-05-21

0 658

51Nod－1202－子序列个数

ACM模版描述题解一道计数DP，递推找规律，可以发现状态转移方程为： dp[i] = (dp[i - 1] * 2 + 1) % MOD; ，该元素首次出现 dp[i] = (dp[i - 1] * 2 - dp[pos[val[i]] - 1] + MOD) % MOD;...

2021-05-21

0 395

51Nod－1391－01串

ACM模版描述题解看到很多人都说这道题是哈希+dp，我看了好久才明白这里所谓的哈希只是一种思想~~~有些傻了，之前一直不知道这种思想叫做哈希。我的dp也有些差劲了，需要加强。以下思路是借鉴一个大牛的（ID：追梦赤子心）：首先，我们可以预处理开头到第i个位置0的数量大于1的数量...

2021-05-21

0 440

51Nod－1412－AVL树的种类

ACM模版描述题解经典的dp，而我却没有想到……树的深度不大，可以实现暴力枚举深度。设dp[i][k]表示结点个数为i，深度为k的AVL个数。那么，状态转移方程为（j表示右子树的结点数目）： 1、dp[i][k] += dp[i - 1 - j][k - 1] * d...

2021-05-21

0 267

51Nod-1455-宝石猎人

ACM模版描述题解十分不错的dp，需要考虑到空间优化问题，否则会爆炸~~~可以使用偏移量的方法（One），也可以预处理跳跃的区间（Two）。当然方法多种多样，貌似使用记忆化搜索也可以过。代码 One： #include <iostream> #include &l...

2021-05-21

0 402

51Nod-1503-猪和回文

ACM模版描述题解万万没想到，这是CF div.2 E题，在51才放在了4级算法，这个世界真奇妙，某大牛说的有趣：难道是通货膨胀的厉害？很好地一道dp题，很无奈，我不会，是参考他人思路写的，很强势！！！一开始想到了dp，也想到了从两端向中间查找，但是细部的处理没有想到合适的手...

2021-05-21

0 366

51Nod-1607-卷积和

ACM模版描述题解虽然不想说，但是还是不得不说，这道题我真的不会，看题解也没有什么觉悟……感觉自己要废了~~~ 看了一个大牛的代码，也是似懂非懂，暂且贴出大牛的代码，题解可以去大牛的链接看，我需要等到自己的造诣再稍微提升些才能搞定这道题了！ Miracle_ma的博客>&g...

2021-05-21

0 441

51Nod-1670-打怪兽

ACM模版描述题解一道十分不错的dp，越发的感觉我的dp好垃圾啊~~~关键是递推思维。官方题解：本题的关键点是发现如果我能在第i轮打败怪物j，那么我一定能在第i+1轮打败怪物j(前提是我还活着)。因此我们可以通过递推来做这题。令dp[i]表示第i轮我仍然存活时的方案综...

2021-05-21

0 499

51Nod-1020-逆序排序

ACM模版描述题解乍一看，逆序数，差点不分青红皂白的就要写归排，还好收住了势头，仔细一看，是dp，然而，我看得出事dp，却因为自己dp用的不够灵活而始终推不出…… 看了相关讨论中Cppowboy的题解，顿悟，好牛逼的说，赞一下~~~ 设f(n,k)表示n个数的排列中逆序数个数为k...

2021-05-21

0 523