HDU--5280(dp或枚举)

简介:
官方题解:
这个题有非常多O(n2)的算法。这里说一种:枚举每个区间,在枚举区间的同一时候维护区间内的最小值和区间和,将最小值与P的大小进行比較,贪心地取最大值就可以。注意若枚举到的区间是整个数组,则P的值是必须取的。
当然也存在O(n)的做法:从左往右处理出dp1[i]=max(a[i],dp1[i1]+a[i]),相同从右往左处理出dp2[i]=max(a[i],dp2[i+1]+a[i])。再枚举要改动哪一个数,用两个数组更新答案就可以。

我是用了两次dp。事实上能够合成一个的,o(n2)的也是,每改一次dp一次,写的略丑。
 
 

}




本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5307023.html,如需转载请自行联系原作者

相关文章
|
8月前
|
索引
【每日一题Day183】LC1187使数组严格递增 | dp
【每日一题Day183】LC1187使数组严格递增 | dp
44 0
|
8月前
|
算法 测试技术
Big Event in HDU(dp算法)
Big Event in HDU(dp算法)
|
8月前
|
算法
算法系列--两个数组的dp问题(2)(上)
算法系列--两个数组的dp问题(2)
38 0
|
8月前
|
算法 计算机视觉
算法系列--两个数组的dp问题(1)(下)
算法系列--两个数组的dp问题(1)
57 0
|
8月前
|
算法
算法系列--两个数组的dp问题(2)(下)
算法系列--两个数组的dp问题(2)(下)
44 0
|
8月前
|
算法
算法系列--两个数组的dp问题(1)(上)
算法系列--两个数组的dp问题(1)
39 0
|
8月前
【每日一题Day182】LC1043分隔数组以得到最大和 | dp
【每日一题Day182】LC1043分隔数组以得到最大和 | dp
53 0
|
存储 算法
dp 就 dp ,数位dp是什么意思 ?
dp 就 dp ,数位dp是什么意思 ?
391 0
洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles(DP)
洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles(DP)
洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles(DP)
HDU-1598,find the most comfortable road(并查集+枚举)
HDU-1598,find the most comfortable road(并查集+枚举)

热门文章

最新文章