加载中
sgu 116

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

2012/05/01 15:25
61
关于拆点法和DP

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

2012/05/14 22:59
89
sgu 149

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

2012/05/07 11:52
127
poj 其他

1014 Dividing dp题,背包 1088 滑雪 经典dp题 1007 DNA Sorting 归并排序求逆序数 1005 I Think I Need a Houseboat 水题 1061 青蛙的约会 同余方程 1004 Financial Management 水题 1011 S...

2012/05/25 08:57
48
环形石子合并问题 - 经典DP问题

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

2012/05/21 10:07
2.2K
sgu 104

背包类型的dp 设f(i,j)为 "将编号1...i的鲜花放到花瓶1...j能够得到的最大吸引力" 对于f(i,j),有两种可能性,要么第j个花瓶是空的,要么第j个花瓶放着编号为i的鲜花 于是可以得到转移方程:...

2012/04/30 11:11
98
最小正连续子序列和 问题

给你一个数组a[1...n],求最小正连续子序列和 这个问题不能用dp解,因为不具有最优子结构。只能尝试其他方法。 常用定义,s[i]为前i个元素的和。那么,任意一个区间和都可以表示成s[j] - s[...

2012/06/23 20:14
238
poj1013 Counterfeit Dollar

还以为是dp。。。果然模拟题才是王道 设 f(i, 0)表示命题“金币i是一个较轻的假币”,f(i, 1)表示命题“金币i是一个较重的假币” 由于只有一个假币,所以最后结果的全集A为 { f(1,0), f(1,1)...

2012/05/27 10:26
78
编辑距离问题 - 经典DP问题

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

dp
2012/05/20 20:10
4.5K
通俗地告诉你:为什么Dijkstra算法是正确的?

通俗地告诉你:为什么Dijkstra算法是正确的? // 大牛可以自动忽略以下内容 ========================================================================== 这里不采用严格数学方法证明,只是...

2012/05/05 00:36
961

没有更多内容

加载失败,请刷新页面

没有更多内容

返回顶部
顶部