存档

文章标签 ‘DP’

POJ 1050 To the Max[DP]

2011年9月13日 没有评论

POJ 2479/2593的拓展,从一维数组变成了二维矩阵,不过我们可以把情况模拟成一维的情况,在DP的基础上需要加上枚举。
题目要求求出给定的一个矩阵的和最大的子矩阵。
我们可以枚举第a行到第c行的情况(假设已经确定矩阵已经确定为最上面为第a行,最下面为第c行),那么只需要确定列的范围即可。我们可以把每一列都求和,这样会得到单独的一行,就可以直接求这一行的最大子段和即可。
POJ 1050 To the Max[DP] 传送:POJ 1050 To the Max http://poj.org[......]

继续阅读

POJ 2479 Maximum sum[DP]

2011年9月12日 没有评论

类似于HDU 1003 Max Sum这一题,只不过这里是说把数组分为两段,把这两段的最大子段和求出来相加,求出最大的这样的值。
方法还是DP,跟HDU1003一样,从i = 0 to n – 1求一次最大子段和,然后从i = n – 1 to 0求一次最大子段和,最后相加判断即可。
POJ 2593 Maximum sum
传送:
POJ 2479 Maximum sum http://poj.org/problem?id=2479
POJ 2593 Max Sequence http://poj.org/p[......]

继续阅读

HDU 1003 Max Sum[DP]

2011年9月12日 1 条评论

水题,很久以前做过的,现在做起来竟然WA了不少次,唉,好久没接触DP了。
这个题就是最大子段和了,不过要求出子段的起始位置和结束位置。答案会有多种,比如某一个连续子段和为0的,要不要算进去,实际上测试的时候算进去和不算进去都是AC的。
状态转移方程:sum[i + 1] = sum[i] > 0 ? sum[i] + num[i + 1] : num[i + 1](这里写成sum[i] >= 0不影响正确性)
下面是AC代码,比较混乱。
HDU 1003 Max Sum[DP] 题目地址:http[......]

继续阅读