mc鲁迅
二月 29, 2008 at 2:13 上午 · Filed under 小心有电
MC重出江湖 继续被acm虐待
这次最先选择的是pku 1456，该题的大概意思就是做有限项选择使目标函数最大化。
首先想到的01背包问题，但是后来发现该题不具有马氏链特征
举例如果有输入数据4 50 2 10 1 20 2 30 1，若通过正向方式则在deadline 1之前的最优解为选择50 2，在deadline 2之前的最优解为30 1 50 2，若考虑顺序问题则在作出50 2的选择后无法选择30 1。逆向方式也有问题 就是选择过多 迭代规模过大
由于输入规模是n<=10000使用的动态规划的方式会使计算复杂度很高 容易超时
其次便是使用贪心算法，每次选择最大利润的选项放在尽量接近其deadline的位置。
开始的想法是正向，以时间递减的方式选择每个时间点的最大利润选项，明显是错误的
例如输入5 10 1 20 1 50 3 60 3 70 3则选择序列应该是20 1 70 3 60 3最优解为70 3 60 3 50 3
后来改为逆向 问题依旧
吃了几个wa后决定搜索资料 找到这篇文章
看来想法还是相近的也是使用贪心，关键在于该文作者首先将利润排序（这个我确实没有想过 呵呵）
而后由利润从高到低尽量放入 直到全部放满为止
该文比较难懂 配合下面的回复才算明白 作者使用了并查集的算法导致比较难看懂 同时效率提高
其实但就算法而言就是对已经排序的有序整数对 对其后项 查找可放入的位置 并放入 直至放满
并查集的作用就是加快这个寻找过程，当然简单的搜索办法也可以奏效，线段树的方法也被提到了。
总结下自己的问题
1 对于贪婪算法的认识表浅–只知道按照次序来 不知道按照大小来
2 对于数据结构的忽视导致了算法优化的困难
先到这里下次补充
追加1：
想了一下这道题如何通过线段树的数据结构做
假设对1-10的时间做如下划分
假设先选择100 9 则将节点[8,9]标记 而后选择90 10 标记[9,10]
这时选择80 10发现[8,10]已经被标记 则选择了[7,8]标记（最接近的空闲节点）
可以发现搜索次数较之直接搜索有所减少
收藏、分享这篇文章！
mc鲁迅
二月 29, 2008 at 12:03 上午 · Filed under 小心有电, 扯淡
诚然linux平台的桌面体验式很差劲的
不稳定（以前提到的xfce面板问题），设置复杂不统一，发行版本多样
gnu有些灰头土脸，什么xgl效果其实都不如简单易用的桌面体验舒适
没有学会走就想跑 m$大叔又要笑了
同样 在winxp下实现双显示器扩展桌面只用点击选项就可以了
然而在xbuntu平台下 则需要修改xorg.conf文件
虽然有自带的图形界面设置可往往导致无效 多次重启未果
再说qq的问题 自从腾讯官方封锁了非官方qq的登录以来在linux平台下使用qq就比较困难了
以前的lumaqq虽然无法填验证码但是用激活辅助还可以勉强使用
而现在eva和lumaqq尽数完蛋 使用wine模拟qq也面临繁多的兼容性问题
难道gnu的使用者还要建立一个gnu的im服务器 以防止哪一天msn yahoo之流全部反水
自身多头 加上外界压力 gnu一路走好啊
收藏、分享这篇文章！
mc鲁迅
二月 26, 2008 at 8:52 上午 · Filed under 户外, 户外装备
约莫一个手掌的长度 号称最坚固的光源到手了
有两个尾盖 一个带挂绳 一个带不锈钢环 前者用于水上是按钮开关 后者水下是旋钮开关
下端看似空心 其实是实心 只在三个led开了小腔体 号称最坚固是有道理的
同样 由于防水尾盖屏弃了按钮 因此个人认为防水还是有保证的
最后 有一点不足 就是使用防水尾盖时因为通过旋转的方式开关 很容易将尾盖拧下 造成误操作
解决办法是–抓住尾盖后的金属环在旋转就ok了 嘎嘎
现在的问题是3.7V的充电cr123a电池可以使用吗
收藏、分享这篇文章！
mc鲁迅
二月 22, 2008 at 8:25 上午 · Filed under 小心有电, 扯淡
1986年有人写了个programmers at work列举了一些当时的顶尖程序员 他们现在如何呢？
随便翻译玩玩
- Charles Simonyi. Then, Microsoft programmer. Now: super-rich guy, space tourist, endowing Oxford chairs and whatnot. Works at Intentional Software. CS同学 MS程序员 发了
- Butler Lampson. Then, PARC dude. Now: a Microsoft Fellow. BL同学 还在打工
- John Warnock. Then: co-founder of Adobe. Now: retired, serves on boards of directors, apparently runs a bed and breakfast. JW同学 adobe的创始人 回家抱孙子流口水了
- Gary Kildall: Then: author of CP/M. Died in 1994. The project he was working on in Programmers at Work became the first encyclopedia distributed on CD-ROM. He also hosted Computer Chronicles for a while.GK同学 1995年翘辫子了
- Bill Gates. Then: founder of Microsoft, popularizer of the word “super”. Now: richest guy in the world. After a stint in the 90s as pure evil, semi-retired to focus on philanthropic work. 比尔盖兹同学 大大的发了 半退休
- John Page. Then: co-founder of the Software Publishing Company, makers of PFS:FILE, an early database program. Now: I’m not really sure. Here’s a video of him from 2006, so he’s probably still alive, but he’s not on the web. SPC was acquired in 1996. Through some odd corporate synergy the public face of the business now appears to be Harvard Graphics. JP同学 software publishing company公司创始人之一 可能活着但是不上网写博什么的鸟
- C. Wayne Ratliff. Then: author of dBase. Now: retired. WR同学 dbase的作者 现在退休了
- Dan Bricklin. Then: co-author of VisiCalc. Now: Has a weblog and lots of accessible historical information about his projects. Still runs Software Garden. Still looks almost exactly like his illustration in PaW, leading some to speculate on a “Spreadsheet of Dorian Gray” type effect. I secretly hope he will see this in referer logs and invite me to hang out with him. DB同学 visiclac作者之一 现在写博客搞搞项目
- Bob Frankston. Then: the other half of VisiCalc. Now: worked for Microsoft for a few years, now retired, has a weblog.BF同学 visicalc的另一作者 为m$卖命几年后退休
- Jonathan Sachs. Then: co-author of Lotus 1-2-3. Now: semi-retired. Gives away Pocket PC software from his home page, and sells photography software as Digital Light & Color. More details in this 2004 oral history. JS同学 lotus 1-2-3的作者之一 现在半退休不做pocketpc了 改卖图形软件
- Ray Ozzie. Then: Lotus Symphony dude, left Lotus to write what would eventually be sold as Lotus Notes. Now: Chief Software Architect at Microsoft, after working for IBM and starting Groove Networks. Has a weblog, but hasn’t posted for about a year. RO同学 微软首席架构师
- Peter Roizen. Then: author of T/Maker, a spreadsheet program. Now: programmer consultant. Inventor of a Scrabble variant that uses shell glob syntax. PR同学 T/Maker作者 现在做顾问鸟
- Bob Carr. Then: PARC Alum, Chief Scientist at Ashton-Tate, author of Framework integrated suite. Now: founder of Keep and Share. In between: co-founded Go, worked for Autodesk. Doesn’t seem to have a web presence.BC同学 ashtom-tate首席科学官 现在是keep and share的创始者
- Jef Raskin. Then: Macintosh project creator, founder of Information Appliance. Died in 2005. His excellent web site is still up. Author of well-respected book The Humane Interface. The project he’s working on in PaW, the SwyftCard, was a minor success. JR同学 macintosh计划创始人 2005年翘辫子了 但是网站还在|||-_-
- Andy Hertzfeld. Then: Macintosh OS developer. Now: works at
the OSAF Google and hosts a bunch of websites, including folklore.org and Susan Kare’s site. (Incidentally, Susan Kare now works for Chumby.) In between: worked at General Magic and Eazel, which probably only people who read this weblog remember. AH同学 Macintosh os的开发者 后来在General Magic工作
收藏、分享这篇文章！
