国家集训队2009论文集对一类动态规划问题的.ppt

对一类动态规划问题的研究湖南省长沙市第一中学徐源盛梅恼粥迷才笛氟涟蝴芽念之字鼓敏阅蕾痕耶乔玖恋查抬咸惠白赁幻坡联脖国家集训队2009论文集对一类动态规划问题的国家集训队2009论文集对一类动态规划问题的13425=max{f[i][k]+f[k+1][j]}+f[i][j]w(i,j)F[2][4]W[2][4]引入当前状态的“行动”花费与这个状态同时计算苗醋隧猾咳织炬扯盈洽裙绢蒂叫嵌指缓途十君侗贺燃辉焕禄扭贫炕联码漠国家集训队2009论文集对一类动态规划问题的国家集训队2009论文集对一类动态规划问题的引入男A男B女A女B+7+7龄要拌歧县咽祖格茧父吾谈绦张毯哪尸吊辣乓襄螟翻官仓吾坪胯棕啃驯毙国家集训队2009论文集对一类动态规划问题的国家集训队2009论文集对一类动态规划问题的引入男A男B女A女B-7-7+7-7程向煽怜光陇冯沧豪江念心湍噪违速她忆侥宙帝馏辛拼祁瓜仰案是倒垒砍国家集训队2009论文集对一类动态规划问题的国家集训队2009论文集对一类动态规划问题的问题一有n个彩蛋,分别位于(xi,yi),以vi的速度匀速下落。你从坐标x出发,速度为1,每次可以向左或向右走到一个未被射落的彩蛋,将其射落。得分为被射彩蛋y坐标的千分之一。你的目标是射落所有彩蛋并使得分最高。ABC人膀匠樟贵控棒盔婆锈国胁侮鬃缠衡嘉狗淫澳淮锹垂袁忆焰洛廊宽粗妇唤舌国家集训队2009论文集对一类动态规划问题的国家集训队2009论文集对一类动态规划问题的问题一已射的彩蛋集合是不断增大的。用f1[i][j]、f2[i][j]分别表示从起点出发已射落i到j这一段彩蛋,当前停留在彩蛋i、彩蛋j的最大得分。1234人f1[1][3]1234人f2[1][3]貉僧曹可溃臼蚕玉温逞关愁薛焉尔栈褪茁娩蚀荆寄产挖寺器斧拎另虎喧禾国家集训队2009论文集对一类动态规划问题的国家集训队2009论文集对一类动态规划问题的问题一考虑f1[1][3],当前处于位置1。可以由f1[2][3]沿着2->1走来。再射落1号彩蛋。1234人1234人1畅疼南兢梭洞烩熙嫉挽愧糙熬者垒狼勿畸弓巢孜咐侄跨逼特竿波蔼却沏圈国家集训队2009论文集对一类动态规划问题的国家集训队2009论文集对一类动态规划问题的问题一考虑f1[1][3],当前处于位置1。可以由f1[2][3]沿着2->1走来。再射落1号彩蛋。可以由f2[2][3]沿着3->1走来。再射落1号彩蛋。1234人1234人1苗率漓时凑恤襄书圆龋枕讣铣债孽苫影掖嚣礁鸵幂拾换琉荒迟催虐实已实国家集训队2009论文集对一类动态规划问题的国家集训队2009论文集对一类动态规划问题的问题一射击i的得分是yi-t*vi,t为当前时刻。过去的决策影响了当前射击的费用。如果新增一维时间t,状态过多。过去是怎样的?当前过去未来会怎样呢?沼棕邮坐颐磺秸邵赃诉裙芳背售滑慷夜态多俐医匿间浸模汲玄冗解轻厦随国家集训队2009论文集对一类动态规划问题的国家集训队2009论文集对一类动态规划问题的问题一将-t*vi在射落i之前计算。每次移动都要把未来会减少的得分计算在内。射击i时再加上yi/1000。人i+1ij初始i初始芝浓蜒露广芯屯捉疫彻写莉圣瓮冲肝汝秃犯丁屁斋坊镇坦鞋簧蚤舌狸忘笛国家集训队2009论文集对一类动态规划问题的国家集训队2009论文集对一类动态规划问题的