2009 年暑假集训讲义 2009 年暑假集训讲义 上海交通大学 马融 上海交通大学 马融 第一讲 穷举与贪心 ................................................................................................................... 3 集市班车 (Fair Shuttle, USACO 2009 Feb) ............................................................................... 4 翻转棋 (Fliptile, USACO 2007 Nov) .......................................................................................... 5 翻转奶牛 (Face The Right Way, USACO 2007 Mar) ................................................................. 6 第二讲 背包问题 ....................................................................................................................... 7 分数膨胀 (Score Inflation, USACO 3.1) .................................................................................... 8 货币系统 (Money Systems, USACO 2.3) .................................................................................. 9 奶牛博览会 (Cow Exhibition, USACO 2003 Nov) ................................................................... 10 太空电梯 (Space Elevator, USACO 2005 Mar) ....................................................................... 11 牛奶量取 (Milk Measuring, USACO 5.3) ................................................................................ 12 第三讲 动态规划选讲 ............................................................................................................. 13 抓苹果 (Apple Catching, USACO 2004 Nov) .......................................................................... 15 最廉回文 (Cheapest Palindrome, USACO 2007 Open) .......................................................... 17 麦香牛块 (Beef McNuggets, USACO 4.1) .............................................................................. 19 道路重建 (Rebuilding Roads, USACO Feb 2002).......................................................
