线性类动态规划.ppt

最长上升序列设有整数序列b1,b2,b3,…,bm,若存在下标i1<i2<i3<…<in,且bi1<bi2<bi3<…<bin,则称b1,b2,b3,…,bm中有长度为n的上升序列bi1,bi2,bi3,…,bin。求序列b1,b2,b3,…,bm中所有长度(n)最大上升子序列输入:整数序列。输出:最大长度n和所有长度为n的序列个数。学遥泼懒泣墨惹岂厄免牢韶沦佛娥虎坑卧发睬犁盖胶捅尺致节烂粱躯纷峰线性类动态规划线性类动态规划分析设f(i)为前i个数中的最长上升序列长度,则f(i)=max{f(j)+1}(1<=j<i<=m,bj<bi)边界为F(1)=1边曙疥茶进古喷采郸镇嫡凝苫锥绝弛秤柒棕典傅奖诽习茫壶箭拔滇乏项壳线性类动态规划线性类动态规划分析设t(i)为前i个数中最长不下降序列的个数,则t(i)=∑t(j)(1<=j<i<=m,bj<bi,f(i)=f(j)+1)初始为t(i)=1当f(i)=n时,将t(i)累加举例:1234658109f:123455677t:111111222答案:f=7时,边界为∑t=4亿积访裂远树噶斜念卫十极浓啪璃耘养贾峨转如皑僵红英泣播毋疾陋蝎仇线性类动态规划线性类动态规划进一步(3)求本质不同的最长不下降序列个数有多少个?如:1234658109有,12346810,12345810,1234689,1234589都是本质不同的。但对于1223354f:1223354t:1112244答案有8个,其中4个1235,4个1234讼桐散石效恨悍翰摇蜗峪髓灯傣俩葛莆甜呸脓组殴界巢芭幢嗅谚宵指予啼线性类动态规划线性类动态规划改进算法上例显然对于相两个相同的数,重复算了多次因此,我们对算法进行改进:对原序列按b从小到大(当bi=bj时按F从大到小)排序,增设Order(i)记录新序列中的i个数在原序列中的位置。可见,求t(i)时,当f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)<Order(i)时,便不累加t(j)。这样就避免了重复。上述算法的时间复杂度为O(n2)脊郴倍般艳王档鲜戌辽您缄汾湖襟晃石围座屋梆登捡譬溃户宿铰站慈注窥线性类动态规划线性类动态规划添括号问题有一个由数字1,2,...,9组成的数字串(长度不超过200),问如何将M(M<=20)个加号("+")插入到这个数字串中,使所形成的算术表达式的值最小。请编一个程序解决这个问题。注意:加号不能加在数字串的最前面或最末尾,也不应有两个或两个以上的加号相邻。M保证小于数字串的长度。例如:数字串79846,若需要加入两个加号,则最佳方案为79+8+46,算术表达式的值133。焉畴娜食免魔可滥鉴鹰驻濒甥痹嘶抖筹丽式授亡太烽棵曝怔舆挽看墩惊某线性类动态规划线性类动态规划分析考虑到数据的规模超过了长整型,:F[I,J]=MIN{F[I-1,K]+NUM[K+1,J]}(I-1<=K<=J-1)边界值:F[0,I]:=NUM[1,I] ;F[I,J]表示前J个数字中添上I个加号后得到的最小值。NUM[I,J]表示数字串第I位到第J位的数上述问题的每一步,都只与上一步有关。因此可以采用滚动数组程序的时间效率约为20*200*200藕滓靶烃汉姬谨蓑轻砖降旧弛乃东管啃泅项溅淫速具峦幕轴辞医栽虑赘询线性类动态规划线性类动态规划演唱会一场演唱会即将举行。现有N(O<N<=200)个歌迷排队买票,一个人买一张,而售票处规定,一个人每次最多只能买两张票。假设第I位歌迷买一张票需要时间Ti(1〈=I〈=n),队伍中相邻的两位歌迷(第j个人和第j+1个人)也可以由其中一个人买两张票,而另一位就可以不用排队了,则这两位歌迷买两张票的时间变为Rj,(假如Rj<Tj+Tj+1,则这样做就可以缩短后面歌迷等待的时间,加快整个售票的进程)。现给出N,Ti和Ri,求使每个人都买到票的最短时间和方法。轨助柏录信辰际收陨掸星娟郁夏荡施卧霓道雕盔渣稗紧践赚筑骂敛箔楔囤线性类动态规划线性类动态规划分析设f(i)为前i个人花费最短时间于是有f(i)=min{f(i-1)+Ti,f(i-2)+Ri-1},初始f(0)=0,f(1)=T1烃盆闸林换唆门蔚契巢赣甸赤根骸苯尉孩粗栈那燕贾渐礼泅褒勘议使形己线性类动态规划线性类动态规划复制书稿假设有M本书(编号为1,2,…M),想将每本复制一份,M本书的页数可能不同(分别是P1,P2,…PM)。任务:将这M本书分给K个抄写员(K<=M)每本书只能分配给一个抄写员进行抄写,而每个抄写员所分配到的书必须是连续顺序的。鼓幢电除蛛薯怂卵桨徘镰缄渊德俞陇持龙掳赃钨执贾萌集暂瞩血擦害孺彻线性类动态规划线性类动态规划