dango

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

POJ2750 Potted Flower(线段树区间更新)

传送门: http://poj.org/problem?id=2750

题目大意:
一堆花围成一圈,每一盆都有自己的attractive value。要你来选一串花,使得总attractive value最大。(题目中有一个非常重要的条件:不可以选所有的花,这个一不注意就功亏一篑了)
每次,有一只坏猫会来把第A盆花的attractive value换成B。坏猫每捣蛋一次,你就要求一个新的总attractive value最大的连续序列。

解题思路:
数据那么大,暴力搞肯定超时了,这种区间最大最小值的问题首先还是应该要想到线段树的。
1 struct tnode 
2 {
3     int sum,mins,maxs;      //当前区间的和、最小子序列和、最大子序列和 
4     int lmin,lmax;          // 当前区间从left出发所能形成的 最小子序列和、最大子序列和 
5     int rmin,rmax;          // 当前区间以right结尾所能形成的 最小子序列和、最大子序列和
6     //int minn;           //当前区间最大最小值 
7 }t[maxn*4];
线段树的节点定下来以后写法差不多也就定了。
每次需要根据孩子的情况来更新父节点的各种值。判断的时候一定要把“转移”(这个挺像动态规划的状态转移的其实……)情况都想齐全,再下手写,写的时候比较容易晕,一定要仔细,避免查错的时候头昏脑胀。
WA了一次,有一个地方没写好。题中说不可以选取所有的花,所以若得到的总attractive value最大的连续序列是整圈的花,就要剪掉整圈花总attractive value最小的连续序列的attractive value和,WA的时候之剪了最小attractive value的一盆花。

代码:(注释掉的一些地方是第一次错的地方,引以为戒~)
POJ2750
posted on 2011-03-05 21:07 Dango 阅读(640) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理