已注销
已注销
全部文章
动态规划
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篇)
HDU-2476-String painter
ACM模版 描述 题解 区间 dp 套路深啊~~~ 首先我们假设用一个空白串儿进行区间 dp 来刷成 B 串。然后我们开始遍历两串,如果 A[i]=B[i] ,那么 ans[i]=ans[i−1] ,否则的话,就需要利用前边处理出来的 dp[][] 来...
2021-05-21
0
349
HDU-2490-Parade
ACM模版 描述 题解 这个题是需要用单调队列优化优化的动态规划问题,好多 OJ 上都有,其中 POJ 数据比较强,需要用输入外挂,并且开 G++ 才能过。 dp[i][j] 表示从最北边到第 i 行第 j 列的最大高兴值,很容易想就是枚举前一行状...
2021-05-21
0
234
HDU-3672-Caves
ACM模版 描述 题解 树型 DP 。 设 dp[i][j][k] 表示以 i 为子树根遍历 j 个结点, k=0 表示遍历结束回到该子树根, k=1 表示不回。 对于 k=0 的情况,当遍历子结点时,可以考虑原本的有返回遍历路径插入对应子结点的有...
2021-05-21
0
393
HDU-3237-Help Bubu
ACM模版 描述 题解 状压 DP 。 设 dp[i][j][k][s] 表示为前 i 本书拿走 j 本剩下的书状态为 k 最后一本书的高度是 s 的最少类数。这里的状态指的是剩下的书所有的高度,而不是剩下的书的序列状态,为什么要这样...
2021-05-21
0
241
UVA-11600-Masud Rana
ACM模版 描述 题解 很神的一个期望状压树型 DP 。 第一步:进行缩点,因为有的点本身就是联通的,所以缩成一个点 x ,并用 cnt[x] 表示这个缩点所拥有的城市个数; 第二步:设 dp[u][st] 表示目前在 u 点的一个城市经过了 ...
2021-05-21
0
416
HDU-3757-Evacuation Plan
ACM模版 描述 题解 设 dp[i][j] 表示前 i 个人疏散进掩体并且第 i 个人疏散进第 j 个掩体里的最小花费。 如此这般,状态转移方程为: dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])+abs(a...
2021-05-21
0
276
HDU-5534-Partial Tree
ACM模版 描述 题解 好恶心的一个翻译题,翻译了半天不知道嘛子意思…… 最后总算是搞懂了,大致说一下,题目要求我们构造一颗包含 n 个结点的树,树的价值为 ∑ni=1f(deg(i)) ,其中 deg(i) 表示结点 i 的度, f(x) ...
2021-05-21
0
458
POJ-3866-Exclusive Access 2
ACM模版 描述 题解 这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。 简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执行任务的等待时间最短。 sdfzyhx’s blog 说可以将资源看成点,任务看成无向边,任务就是把无向边定向,使图中不存在环并且...
2021-05-21
0
287
51Nod-1636-教育改革
ACM模版 描述 题解 按照课程复杂度从小到大进行排序,设 dp[i][j][k] 表示前 i 门课程选择了 j 门并且第 j 门课程为 i ,并且课程 i 布置的作业数量为 a[i]+k 时的最大总作业量。 代码...
2021-05-21
0
265
POJ-3744-Scout YYF I
ACM模版 描述 题解 分段 + 概率 DP + 矩阵加速。 首先,题目给了雷的数目至多只有十个,不算多,可以将全程进行分段,保证每段只有一个雷或者多个雷在一个位置,并且雷的位置都是段尾。 分段后,每一段之间都是独立的,求出安全通过每一段的概率,最后根据乘法原理即可求出整段的概率。...
2021-05-21
0
192
首页
上一页
6
7
8
9
10
11
12
13
14
15
下一页
末页