已注销

动态规划

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-1705-七星剑

ACM模版描述题解期望 DP 。这里用 lose_[i][j] 表示镶嵌第 i 个孔用第 j 种宝石失败后会返回的宝石框的位置，dp[i] 镶嵌成功第 i 颗宝石的期望，那么对于第 j 种宝石来说，我们会得到如下方程： ...

2021-05-21

0 460

51Nod-1779-逆序对统计

ACM模版描述题解虽然一眼就看出来了状压 dp，但是再往后我就不知道从何下手了，有些懵逼，不是太清楚如何转移。找了找官方题解，发现我果然想不到这个，但是我依然无法按照题解的提示写出来，这就尴尬了，好在网上很多大神写过这个博客，我就参考了一下他们的代码，我只想说…… ╮(╯▽╰)...

2021-05-21

0 372

51Nod-1500-苹果曼和树

ACM模版描述题解树形DP，状态转移方程不是特别容易想。我们先设置 dp[i][0/1] 表示以当前节点 i 为根的子树且包含该根的联通块儿的方案数，方案数划分为两部分，一部分是不包含黑色的方案数，另一种则包含一个黑色。这样子我们可以分析出来联通块儿之间的关系，假设两...

2021-05-21

0 396

51Nod-1510-最小化序列

ACM模版描述题解这个题，打眼一看就是贪心，然后我就贪心写了一下， WA 了三分之一，分析了一下，感觉只是贪心不行，还有 dp 搞搞才行…… 首先，贪心的思路是，我们需要将数据分为 k 组，其中有 n % k 组的大小为 nk+1 ，剩下的 k−n...

2021-05-21

0 431

51Nod-1673-树有几多愁

ACM模版描述题解真的感觉这个题好难，看了官方题解也不知道怎么搞，又找了一下代码，稍微懂了一些……总得来说，这个题就是 dp （树归、状压） + 贪心，贴一下官方题解吧……我也说不好。真废…… 代码 #include <cstdio> #include <...

2021-05-21

0 414

51Nod-1780-完美序列

ACM模版描述题解首先，我们先来分析一下如何构造才合法。先预处理出来每种大小的数的个数，并在这个过程进行判断是否连续（不大于 1 ），然后，我们可以从小到大进行插空法插数，那么如何插呢？假如，此时我们已经查到数 i ，那么合法的插孔分为两种，第一种是插在两个 ...

2021-05-21

0 398

51Nod-1684-子集价值

ACM模版描述题解这个 dp 好难理解…… 官方题解：似懂非懂还装懂的样子☺(^__^) 代码 #include <cstdio> #include <cstring> #include <algorithm> using n...

2021-05-21

0 271

51Nod-1623-完美消除

ACM模版描述题解这个题着实难住了我，虽然知道是数位 dp，但是依然是手足无措，找了光速小子0511 的代码，看了一下，神还原题解啊，必须点赞，太崇拜了…… 官方题解：这个官方题解有一个小小的玩笑，我想机智的你仔细看一定是可以看出来的，尽管我没有看出来，我还是看到了讨论区...

2021-05-21

0 376

51Nod-1522-上下序列

ACM模版描述题解十分巧妙的一道动态规划问题，应该算是区间 dp 吧！首先我们需要考虑，大的数应该更趋向于中间，而小的数则是在两边，所以我们不妨从大到小遍历，不断往已有序列进行插入，插入的方式决定了状态的转移，每次插入的时候我们都同时插入两个，插入方式有三种：两端、首、尾，每...

2021-05-21

0 298

HDU-2017 多校训练赛1-1003-Colorful Tree

ACM模版描述题解其实这就是一道树归题而已，比赛时就知道，但是时间不够写了……给一下官方题解吧~~~ 单独考虑每一种颜色，答案就是对于每种颜色至少经过一次这种的路径条数之和。反过来思考只需要求有多少条路径没有经过这种颜色即可。直接做可以采用虚树的思想（不用真正建出来），对每种...

2021-05-21

0 348