加载中
poj 1821 - dp,单调队列

终于做出这题了!泪流满面啊。 首先,要理解清楚题目意思。有一道线性篱笆由N个连续的木板组成。你手上有K个工人,你要叫他们给木板涂色。每个工人有3个字段:L 表示 这个工人可以涂的最大木...

2012/06/02 23:21
451
POJ2373 - 单调队列

这题的细节好多。。。。 首先,因为一个花丛区间是不能同时被两个木板覆盖的,所以,我们要把那些有交集的花丛区间都合并到一个花丛区间,这是第一步。 从这里开始,接下来,我们讨论中出现的...

2012/05/31 08:39
377
单调队列

简单来说,单调队列是用来解决这样的问题的: 实现一个目标容器buffer,支持3种操作: 不断地向buffer里读入元素、 时不时会去掉当前buffer里的最老的元素 不定期地询问当前buffer里的最小元...

2012/05/29 14:59
218
poj1015 Jury Compromise - dp,背包模型

以前年少无知,看到这题觉得无从入手,今天,终于看出来,这是一道背包题。 每个人,只有选和不选,如果选了,就会影响某个资源的值,而且人与人之间的顺序不影响答案,这种类型的题目,果断...

2012/05/27 08:34
175
环形石子合并问题 - 经典DP问题

============================================================ 又是一道超经典的题目。 对于线性的合并石子问题,dp模型类似于“加括号”那类型的dp题目,设 f(i, j)为 将第i项到第j项合并...

2012/05/21 10:07
2.2K
编辑距离问题 - 经典DP问题

这题必须好好写一下心得。这题包含很多“剪切粘贴”技术,这是一种强化题目条件,并且不会改变问题最终答案的技巧。 先设A的长度为LA,B的长度为LB,并且第一个字符的编号为1。 这种类型的d...

dp
2012/05/20 20:10
4.5K
序关系计数问题

这题以前做过,印象还是挺深刻的。 如果我们把不同的变量看成是不同的小球,如果两个变量相等的话,那么对应的小球就在同一个箱子里(箱子们有序地排成一行)。那么,原问题就等价于: 将n个...

2012/05/20 16:01
138
独立任务最优调度问题

本来想着用f(i)来表示把作业1...i都完成需要的最少时间,发现转移不了,状态太粗糙了,于是要加维。 用布尔变量 f(n,i,j)表示 能否把作业1...n都完成,而且在机器A上消耗的时间为i,在...

2012/05/20 14:48
117
漂亮打印

简单题目。 设 f(i)表示将 单词1 到单词i 这i个单词打印到若干行的最小代价,而且,这个最小代价也包括最后一行的额外空格,后面会说明为什么要这样定义。 再设w(a, b) 表示 将单词a ,a+1...

2012/05/20 11:40
73
关于拆点法和DP

拆点法和DP增加维数,动机是一样的,就是状态表示太粗糙,以至于无法转移或者求出问题的答案,所以要将一个状态拆成多个更细更具体的状态,一般的做法是,缺啥就添啥,也就是说,如果你发现:...

2012/05/14 22:59
89
sgu 183 - DP,滚动数组

这题要好好总结一下,有太多东西要学了,先开个坑 #include <algorithm> #include <vector> #include <cstdio> using namespace std; template <class VVType, class T> void make2DVector(V...

2012/05/13 11:42
206
sgu 149

第一次做树形dp,居然1Y了,而且发现注释真是好东西,写了注释自己也不容易犯错。对于DP来说更是如此,因为DP的状态表述得越不含糊,就越不容易写错转移方程。 dp说到底就是递推,往前推或者...

2012/05/07 11:52
127
sgu 168

这题本来以为很容易可以过,结果在test 3 WA了好多次 这题有个很容易想漏的地方。 首先,画个图,搞清楚B[i][j]的含义。 一开始,会想到转移方程应该就是 B[i][j] = min { A[i][j], B[i+1][...

2012/05/06 11:00
101
sgu 116

本来是一题很简单的背包题, 结果老是RTE, 看了别人的题解, 最后才搞定, dp题吐血啊.... 首先,要搞出dp转移方程, 其次,要考虑,对于问题的所有输入, 是否都经过你编写的dp的那部分代码, 这个很...

2012/05/01 15:25
61

没有更多内容

加载失败,请刷新页面

没有更多内容

返回顶部
顶部