acm動態(tài)規(guī)劃入門ppt課件(編輯修改稿)
2025-06-01 07:49 本頁面
【文章內容簡介】 這樣一直推到 f(len(a),len(b))就得到所要求的解了 . f(i1,j1)+1 (a[i]==b[j]) max(f(i1,j),f(i,j1)) (a[i]!=b[j]) 子結構特征： 2022/6/2 17 四、 經(jīng)典問題 ： 1421 搬寢室 Sample Input 2 1 1 3 Sample Output 4 2022/6/2 18 ? 搬寢室是很累的 ,xhd深有體會 .時間追述 2022年 7月 9號 ,那天 xhd迫于無奈要從 27號樓搬到 3號樓 ,因為 10號要封樓了 .看著寢室里的 n件物 品 ,xhd開始發(fā)呆 ,因為 n是一個小于 2022的整數(shù) ,實在是太多了 ,于是 xhd決定隨便搬 2*k件過去就行了 .但還是會很累 ,因為 2*k也不小是一個不 大于 n的整數(shù) .幸運的是 xhd根據(jù)多年的搬東西的經(jīng)驗發(fā)現(xiàn)每搬一次的疲勞度是和左右手的物品的重量差的平方成正比 (這里補充一句 ,xhd每次搬兩件東西 , 左手一件右手一件 ).例如 xhd左手拿重量為 3的物品 ,右手拿重量為 6的物品 ,則他搬完這次的疲勞度為 (63)^2 = 的 xhd希望知道搬完這 2*k件物品后的最佳狀態(tài)是怎樣的 (也就是最低的疲勞度 ),請告訴他吧 . 2022/6/2 19 第一感覺： ? 根據(jù)題目的要求，每次提的兩個物品重量差越小越好，是不是每次提的物品一定是重量相鄰的物品呢？ ? 證明：假設四個從小到大的數(shù)： a、 b、 c、d，只需證明以下表達式成立即可： ? (ab)^2+(cd)^2 (ac)^2+(bd)^2 ? (a
教學課件相關推薦
鄂ICP備17016276號-1