2018CCPC网络预选赛1010/hdu6447 离散化/DP/线段树

http://acm.hdu.edu.cn/showproblem.php?pid=6447

题意:
从(0,0)(0,0)走到(10^9,10^9)(10^9,10^9),其中每次只能往(x+1,y),(x+1,y+1),(x,y+1)三个目标走,期间有n个村庄,但每个村庄只能从其(x-1,y)或(x,y-1)走到其上才能获得该村庄的金钱vk,问最后可以获得的最大金钱

分析:
最大值规划问题很自然的会想到用DP做,但此处单纯对每个城镇进行DP的话每次需要遍历所有城镇,复杂度是O(n^2),难以解决.
另一个想法是以坐标作为基准进行DP,这样的话我们需要先将城镇坐标进行离散化,然后用dp[n]储存到达第n列时达到的最大金钱,并将城镇按照从上到下,从右到左进行排序.
之后迭代遍历每个城镇,对于第n列的某城镇k,dp[n]=max(dp[n],max(dp[1~n-1)+vk),城镇的排列顺序保证了迭代完成后dp[]能计算出到达每一列时的最大金钱,而区间查询可以使用线段树或树状数组进行优化,
最终达到的复杂度为O(nlogn)

代码如下:(事实上由于这个线段树写的特别渣,导致最终通过时间大概是990ms左右,也有TLE的可能…)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据