图上的动态规划

题目描述

陶陶假期的时候独自去天津玩,出发前他想制定一个旅行计划。假设天津有N个景点,陶陶给每个景点定义了一个开心值Si,也就是说当他游玩这个景点后他的总开心值会加Si,同时,游玩第i个景点会花费Ci的时间。由于没有基友陪,所以他想在限定的时间T内,从起始点S,有选择的游览一些景点,最后到达终点E。当然他想让这次旅行所得的开心值最大。

Read More

斜率优化动态规划

题目描述

在一条直线上有n处地方,从左到右依次编号为1, 2, …, n,每处地方都有一定量的煤,每处地方的单位量煤运送单位距离都需要一定的费用,例如在1处有数量为a的煤,单位量的煤运送单位距离的费用是b,那么把这么多煤一共运送c的距离所需要的费用为abc。现在需要把这n处地方的煤送往加工中心处理,为了使得路径单一,所有地方的煤只能向右边(编号较大的地方的方向)运送,已知第n处的地方已经存在了一个加工中心。为了减少煤运送的费用,在这条路径上最多可以添加k个加工中心,使得总运费最少。问最小的运费是多少?(CEOI 2004改编)

Read More

C++ STL中平衡树在算法题目的应用

题目描述•其一

给定一个长度为n的数组s,数组s的子串s[i,j]表示s[i],s[i+1],s[i+2]……s[j]。求最大长度的子串,该子串必须满足:m1<=max(s[i],s[i+1]……s[j])-min(s[i],s[i+1]……s[j])<=m2。如果最大长度的子串有多个,请找出子串和最大的那个。对于子串[i,j],子串和指的是sum(s)=s[i]+s[i+1]+s[i+2]+……s[j],子串长度指的是length=j-i+1。如果没有子串满足,请输出”0 0”。

Read More

我的故事——创建小组篇

––起源

从小就很容易对新事物产生好奇,大自然的泥巴、高耸的树木、静静的小溪、湍急的河流,人工制造的玩具车,工具箱里的各类器械。偶尔也用废弃的砖头垒点什么。当然也对家里的一台古旧的计算机产生好奇,时间是上世纪90年代。我还在学龄前,父亲不知是从中关村还是鞍山西道带回家2张少儿百科光盘。界面是类似游乐园的样子,点击上面某个游玩项目就会进入一个主题,有讲解人体结构的、有讲解桥梁和火车铁道的、也有讲解动植物的,带上稳重的配音我看得津津有味。伴随着年龄的增长,渐渐的,我也想去学习如何使用计算机。最开始是学习如何使用Windows系统自带的画图软件,一玩就是一整天。

上了小学后,除了《Windows画图》还有《金山画王》和另一个我忘记名字的少儿绘画软件(我更偏爱这一个),灵感得到了充分的激发与释放。那时候购买的软件都是有实体光盘的,通常被一个大盒子包裹,包装上写着详尽的介绍和系统要求,盒子里面有说明书和光盘。我还记得说明书上印着《剑侠情缘》、《博德之门》和《金山游侠》的广告。看着当时的电视节目《游戏东西》中介绍的一些作品,类似的实体游戏和软件我不知购买了多少,偶尔也会去报刊亭捎上一本计算机或游戏机杂志。

一次偶然的契机父亲带我去书店购买了一本长宽比大概在2:1,看上去很窄,每页只有两幅图和一段配文的《PPT制作》书籍。读起来浅显易懂,只需要按照上面的步骤照猫画虎即可。制作PPT带来的成就感勾起了我对计算机学习的极大兴趣和热情。学会使用PPT之后,为了继续深入,购买了《洪恩》系列开始学习用Frontpage做网站。电脑水平逐渐提高,网页三剑客、《Authorware动感多媒体自己制》都不能让我满足。那段日子除了学做网页,也会学习如何安装Windows 2000、XP、Red Hat Linux操作系统,56K/ADSL拨号上网(了解了Netscape和IE的恩怨情仇),就连学校也会组织小学生去一个劳技实践办事处让大家伙在机房里用网络聊天室聊天。

夏日,目不转睛的盯着计算机屏幕,对精彩而未知世界的不断探索携带着对美好未来的期望让我深深不得自拔。

Read More

我的故事——竞赛篇

––曲折道路上的追梦者,仅部分片段。

––孩童时期是一个非常普通的竹篱茅舍的毛小子,爱好玩耍,不懂读书。最喜欢夏天穿着短裤光着小脚在牵牛花的陪伴下,走向田野,附和着成荫绿树的影子,在乡间的小溪边荡漾。摇曳着清风的线条,我能抓住的不只是蜻蜓和蚂蚱,还是那未到的盛夏,偶尔下着小雨,土地就会变成了贪玩孩子的梦想泥潭。我很喜欢清风,尤其是夏天出来乘凉,刮过的沁人心脾的夜风,毕竟抬头就是银河,一望无际的夜空,美丽的闪烁着的星体和月亮。我是那么的喜欢星空,感觉在浩瀚无垠的宇宙面前,一切都升华了,所以小时候我第一个梦想就是天文学家……

Read More