算法合集之《淺談貪心思想在動態(tài)規(guī)劃中的應(yīng)用》.doc

2006 年全國信息學(xué)冬令營講座 1 貪婪的動態(tài)規(guī)劃貪婪的動態(tài)規(guī)劃 淺談貪心思想在動態(tài)規(guī)劃中的應(yīng)用淺談貪心思想在動態(tài)規(guī)劃中的應(yīng)用 浙江省紹興縣柯橋中學(xué) 黃勁松 關(guān)鍵字關(guān)鍵字 貪心法 動態(tài)規(guī)劃 狀態(tài) 時間復(fù)雜度 摘要摘要 貪心法和動態(tài)規(guī)劃是信息學(xué)競賽中的兩種常用算法 本文著重討論了貪心 的思想是如何巧妙的運用到動態(tài)規(guī)劃的解題中的 全文分三個部分 首先討論 了貪心思想運用到動態(tài)規(guī)劃解題中的可行性和必要性 然后就貪心思想在動態(tài) 規(guī)劃中的兩種基本應(yīng)用分別做了舉例說明 最后總結(jié)全文 正文正文 引言引言 貪心法和動態(tài)規(guī)劃是信息學(xué)競賽中的常用經(jīng)典算法 而當某些問題的模型 過于復(fù)雜的時候 由于狀態(tài)過于龐大 轉(zhuǎn)移困難等一系列的問題 常規(guī)的動態(tài) 規(guī)劃難于甚至無從下手 而在這個時候 巧妙的使用貪心思想 將其融入到動 態(tài)規(guī)劃的解題中 動態(tài)規(guī)劃便煥發(fā)出了新的光彩 1 1 貪心思想運用到動態(tài)規(guī)劃中的必要性和可行性 貪心思想運用到動態(tài)規(guī)劃中的必要性和可行性 動態(tài)規(guī)劃的原理是 在求解問題的過程中 通過處理位于當前位置和所達 目標之間的中間點來找到整個問題的解 整個過程是遞歸的 每到一個新的中 間點都是已訪問過的點的一個函數(shù) 適合于動態(tài)規(guī)劃法的標準問題必須具有下 列特點 1 整個問題的求解可以劃分為若干個階段的一系列決策過程 2 每個階段有若干可能狀態(tài) 3 一個決策將你從一個階段的一種狀態(tài)帶到下一個階段的某種狀態(tài) 4 在任一個階段 最佳的決策序列和該階段以后的決策無關(guān) 5 各階段狀態(tài)之間的轉(zhuǎn)換有明確定義的費用 在實際的動態(tài)規(guī)劃的解題中 面臨著兩大困難 一是不知道題目是否可以 用動態(tài)規(guī)劃求解 二是即使能夠想到用動態(tài)規(guī)劃來求解 但是因為種種因素 算法的效率并不樂觀 這個時候 使用貪心思想分析問題 可以讓你在山窮水 盡疑無路的時候 柳暗花明又一村 在運用貪心思想的時候 主要是分析出問題的一些本質(zhì) 或者分析出低效 算法的一些冗余 當然 我們要根據(jù)題目的特殊信息 合理的運用好貪心思想 才能幫助動態(tài)規(guī)劃發(fā)揮其強大的功效 2006 年全國信息學(xué)冬令營講座 2 下文就貪心思想如何解決動態(tài)規(guī)劃面臨著的這兩大困難分別做了舉例說明 2 2 貪心思想在動態(tài)規(guī)劃中的應(yīng)用一 貪心思想在動態(tài)規(guī)劃中的應(yīng)用一 確立狀態(tài)確立狀態(tài) 動態(tài)規(guī)劃當中 狀態(tài)的確立是重點 而在實際的解題過程中 狀態(tài)的信息 往往是隱含的 這個時候 合理的運用貪心思想 可以迅速的從繁蕪叢雜的問 題背景中巧妙地抽象出狀態(tài) 我們通過下面的例子來看一看 貪心思想是如何 幫助動態(tài)規(guī)劃確立狀態(tài)的 例題一例題一 青蛙的煩惱青蛙的煩惱 1 1 題目大意 題目大意 池塘里有 n 片荷葉 1 n 1000 它們正好形成一個凸多邊形 按照順時針 方向?qū)⑦@ n 片荷葉順次編號為 1 2 n 有一只小青蛙站在 1 號荷葉上 它想跳過每片荷葉一次且僅一次 它可以 從所站的荷葉跳到任意一片荷葉上 同時 它又希望跳過的總距離最短 請你編程幫小青蛙設(shè)計一條路線 算法分析 算法分析 問題似乎是一個 N 個點的 TSP 問題 2 但卻又是一個特殊的 TSP 問題 題目中說明 N 個點圍成了一個凸多邊形 如何合理的運用這個特殊的條件成為了解題的關(guān)鍵 原始的問題模型很容易使人放棄動態(tài)規(guī)劃 因為狀態(tài)難以抽象 狀態(tài)轉(zhuǎn)移 也無從著手 但如果從問題特征出發(fā) 靈活運用貪心策略 卻能巧妙的設(shè)計出 一種高效的動態(tài)規(guī)劃算法 先介紹一下 TSP 問題的一種局部搜索算法 2 最優(yōu)算法 它從隨機的一 種可選路徑出發(fā) 稱為路徑 T 試圖去改善它 我們在 T 中尋找出 2 條不相交 的邊 移動這兩條邊 如果新產(chǎn)生的路徑比原來的路徑優(yōu)秀 那么就移動這兩 條邊 這種移動稱為 2 交換 如圖所示 可以根據(jù)這個 TSP 問題的局部最優(yōu)算法容易想到 原問題的最短路線中顯 然不存在相交的邊 否則一定可以將這條路線 改進 成一條更優(yōu)秀的路線 1 經(jīng)典問題 2 經(jīng)典的旅行商問題 NP 問題 2006 年全國信息學(xué)冬令營講座 3 根據(jù)上述結(jié)論可以知道 從 1 出發(fā)的第一步只能到 2 或者 n 否則產(chǎn)生的 路線一定不會是最優(yōu)的 因此 原問題的模型變成了 尋找以 1 為起點 遍歷凸多邊形 1 N 中的頂 點一次且一次的最短路線 根據(jù)上述結(jié)論可以知道 如果離開 1 到達 2 接下 來的任務(wù)是尋找以 2 為起點 遍歷凸多邊形 2 N 中的頂點一次且一次的最短路 線 如果離開 1 到達 N 接下來的任務(wù)是尋找以 N 為起點 遍歷凸多邊形 2 N 中 的頂點一次且一次的最短路線 這是一個遞歸的過程 因此 狀態(tài)可以這樣表示 f i L 0 表示從 i 出發(fā) 遍歷 i i L 1 中的頂點一 次且一次的最短距離 f i L 1 表示從 i L 1 出發(fā) 遍歷 i i L 1 中的頂點一次且 一次的最短距離 狀態(tài)轉(zhuǎn)移方程是 f i L 0 min dist i i 1 f i 1 L 1 0 dist i i L 1 f i 1 L 1 1 f i L 1 min dist i L 1 i L 2 f i L 1 1 dist i L 1 i f i L 1 0 f i 1 0 0 f i 1 1 0 其中 dist a b 表示第 a 個結(jié)點和第 b 個結(jié)點之間的歐幾里德距離 問題的 答案是 f 1 n 0 時間復(fù)雜度 O n2 本題小結(jié) 本題小結(jié) 本題中運用貪心思想合理的分析出了問題最優(yōu)解的一些特點 從而能夠根 據(jù)問題中的特殊條件確立出動態(tài)規(guī)劃的狀態(tài) 把看似 NP 的問題 用動態(tài)規(guī)劃 巧妙的解決了 例題二例題二 The Horse Racing 3 3 題目大意 題目大意 中國古代的歷史故事 田忌賽馬 是為大家所熟知的 話說齊王和田忌又 要賽馬了 他們各派出 N 匹馬 N 2000 每場比賽 輸?shù)囊环綄⒁o贏的一 方 200 兩黃金 如果是平局的話 雙方都不必拿出錢 現(xiàn)在每匹馬的速度值是 固定而且已知的 而齊王出馬也不管田忌的出馬順序 請問田忌該如何安排自 己的馬去對抗齊王的馬 才能贏最多的錢 3 上海賽區(qū) 2004 年 ACM 比賽試題 2006 年全國信息學(xué)冬令營講座 4 算法分析 算法分析 這個問題很顯然可以轉(zhuǎn)化成一個二分圖最佳匹配的問題 把田忌的馬放左 邊 把齊王的馬放右邊 田忌的馬 A 和齊王的 B 之間 如果田忌的馬勝 則連 一條權(quán)為 200 的邊 如果平局 則連一條權(quán)為 0 的邊 如果輸 則連一條權(quán)為 200 的邊 然而我們知道 二分圖的最佳匹配算法的復(fù)雜度很高 無法滿足 N 2000 的要求 我們不妨用貪心思想來分析一下問題 因為田忌掌握有比賽的 主動權(quán) 他總是根據(jù)齊王所出的馬來分配自己的馬 所以這里不妨認為齊王的出馬順序 是按馬的速度從高到低出的 由這樣的假設(shè) 我們歸納出如下貪心策略 1 如果田忌剩下的馬中最強的馬都贏不了齊王剩下的最強的馬 那么 應(yīng)該用最差的一匹馬去輸給齊王最強的馬 2 如果田忌剩下的馬中最強的馬可以贏齊王剩下的最強的馬 那就用 這匹馬去贏齊王剩下的最強的馬 3 如果田忌剩下的馬中最強的馬和齊王剩下的最強的馬打平的話 可 以選擇打平或者用最差的馬輸?shù)舯荣?第一個貪心策略的證明 此時田忌的所有馬都贏不了齊王的馬 所以無論用最慢馬去輸還是用最快 的馬去輸都同樣是輸 而處于貪心的思想 我們應(yīng)該保留相比之下更強的馬 因此用最慢的馬去輸一定不會比用別的馬去輸來得劣 所以這是最優(yōu)策略 證畢 第二個貪心策略的證明 假設(shè)現(xiàn)在齊王剩下的最強的馬是 A 田忌剩下的最強的馬是 B 如果存在 一種更優(yōu)的比賽策略 讓 B 的對手不是 A 而使得田忌贏更多的錢的話 那么 設(shè)此時 A 的對手是 b B 的對手是 a 1 若 b A 則有 B a b A 這個結(jié)果和 B A b a 是相同的 2 若 aa b A 這個結(jié)果不如 B A b a 來得優(yōu)秀 3 若 b a A 則有 B a b A 這個結(jié)果和 B A b a 是相同的 由此可知 交換各自對手后 一定不會使得結(jié)果變劣 那么假設(shè)是不成立的 證畢 第三個貪心策略的證明 因為田忌最快的馬也只是和齊王的馬打平 那么田忌只能選擇平或輸 選 擇平的話 當然只能用最快的馬去平了 選擇輸?shù)脑挳敃r是用最慢的馬去輸來 得值得 這和第一個貪心策略的思路是一樣的 證畢 我們發(fā)現(xiàn) 第三個貪心策略出現(xiàn)了一個分支 打平或輸?shù)?如果窮舉所有 的情況 算法的復(fù)雜度將比求二分圖最佳匹配還要高 如果一概而論的選擇讓 最強的馬去打平比賽或者是讓最差的馬去輸?shù)舯荣?則存在反例 2006 年全國信息學(xué)冬令營講座 5 光是打平的話 如果齊王馬的速度分別是 1 2 3 田忌馬的速度也是 1 2 3 每次選擇打平的話 田忌一分錢也得不到 而如果選擇先用速度為 1 的馬輸給速度為 3 的馬的話 可以贏得 200 兩黃金 光是輸?shù)舻脑?如果齊王馬的速度分別是 1 3 田忌馬的速度分別是 2 3 田忌一勝一負 仍然一分錢也拿不到 而如果先用速度為 3 的馬去 打平的話 可以贏得 200 兩黃金 雖然因為第三個貪心出現(xiàn)了分支 我們不能直接的按照這種方法來設(shè)計出 一個完全貪心的方法 但是通過上述的三種貪心策略 我們可以發(fā)現(xiàn) 如果齊 王的馬是按速度排序之后 從高到低被派出的話 田忌一定是將他馬按速度排 序之后 從兩頭取馬去和齊王的馬比賽 有了這個信息之后 動態(tài)規(guī)劃的模型 也就出來了 設(shè) f i j 表示齊王按從強到弱的順序出馬和田忌進行了 i 場比賽之后 從 頭 取了 j 匹較強的馬 從 尾 取了 i j 匹較弱的馬 所能夠得到的最大盈 利 狀態(tài)轉(zhuǎn)移方程如下 1 1 1 1 max ijgjifijingjifjif 其中 g i j 表示田忌的馬和齊王的馬分別按照由強到弱的順序排序之后 田 忌的第 i 匹馬和齊王的第 j 匹馬賽跑所能取得的盈利 勝為 200 輸為 200 平為 0 本題小結(jié) 本題小結(jié) 雖然本題存在直接貪心的方法 不過它可以作為一個例子告訴大家 合理 的運用貪心策略 分析出問題的一些本質(zhì)之后 一些看似不能用動態(tài)規(guī)劃做的 題目便可以巧妙的確立出狀態(tài) 繼而可以用動態(tài)規(guī)劃來求解 3 3 貪心思想在動態(tài)規(guī)劃中的應(yīng)用二 貪心思想在動態(tài)規(guī)劃中的應(yīng)用二 優(yōu)化算法優(yōu)化算法 一些動態(tài)規(guī)劃的題目雖然容易確立出正確的狀態(tài)以及輕松的寫出狀態(tài)轉(zhuǎn)移 方程 但是直序的算法往往效率不高 而貪心歷來都是與 高效 一詞分不開 的 所以 合理的在動態(tài)規(guī)劃中運用貪心思想 能夠讓原本效率低下的算法獲 得 重生 例題三例題三 石子歸并石子歸并 4 4 題目大意 題目大意 在一個操場上擺放著一排 n n 1000 堆石子 現(xiàn)要將石子有次序地合并 成一堆 規(guī)定每次只能選相鄰的 2 堆石子合并成新的一堆 并將新的一堆石子 數(shù)記為該次合并的花費 試編程求出將 n 堆石子合并成一堆的最小花費 算法分析 算法分析 這是一道經(jīng)典的動態(tài)規(guī)劃問題 用 m i j 表示第 i 堆石子合并到第 j 堆石子 所需的最小花費 w i j 表示第 i 堆石子到第 j 堆石子的石子總數(shù) 狀態(tài)轉(zhuǎn)移方 4 經(jīng)典問題 2006 年全國信息學(xué)冬令營講座 6 程如下 1 min jiwjkmkimjim jki 上述算法的狀態(tài)總數(shù)為 O n2 每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為 O n 每次狀態(tài)轉(zhuǎn) 移的時間為 O 1 所以總的時間復(fù)雜度為 O n3 顯然 這個簡單易懂的算法的過于低效了 我們需要進行優(yōu)化 我們嘗試尋找動態(tài)規(guī)劃中的冗余 不難發(fā)現(xiàn) 在枚舉決策 k 的時候 上述 算法實在是太盲目了 因為當有一些 k 如果作為決策點 肯定得不到最優(yōu)解 我們可以不去枚舉他們 這是一種貪心的思想 令 s i j 表示使得 m i j 取到最小時的 k 可以用四邊形不等式 5證明出 s i j s i j 1 s i 1 j 1 i j 這說明 m i j 的決策單調(diào) 于是狀態(tài)轉(zhuǎn)移方程可以變成如下的形式 1 min 1 1 jiwjkmkimjim jiskjis 整體的時間復(fù)雜度則變?yōu)榱?2 1 1 1 11 1 1 1 1 1 nOinsnisinOjisjisO n i n i n ij 本題的相關(guān)證明詳見參考文獻 3 本題小結(jié) 本題小結(jié) 決策單調(diào)的動態(tài)規(guī)劃是一類很常見的問題 例如 NOI2004 的 hut 就是一道 不錯的根據(jù)決策單調(diào)的性質(zhì)來優(yōu)化動態(tài)規(guī)劃的題目 根據(jù)決策單調(diào)的性質(zhì) 我 們避免了一些無用的決策枚舉 從而使得算法的復(fù)雜度降了級 這是貪心思想 的經(jīng)典體現(xiàn) 例題四例題四 The Lost House6 6 題目大意 題目大意 蝸牛的房子遺失在了一棵樹的某個葉子結(jié)點上 它要從根結(jié)點出發(fā)開始尋 找它的房子 有一些中間結(jié)點可能會住著一些蟲子 這些蟲子會告訴蝸牛它的 房子是否在以這個中間結(jié)點為根的子樹上 這樣蝸牛就不用白跑路了 當然 如果有些結(jié)點沒有住著蟲子的話 那么可憐的蝸牛只有靠自己決定訪問順序來 探索了 假設(shè)蝸牛走過一條邊的耗費都是 1 且房子遺失在每個葉子結(jié)點的概 率都是相等的 那么請問蝸牛找到他的房子的最小數(shù)學(xué)期望值 我們約定 樹上的結(jié)點數(shù) n 最多為 1000 每個結(jié)點的分叉數(shù) k 最多為 8 例如在下面的這棵樹當中 5 當函數(shù) w i j 滿足 時 稱 w 滿足四邊形不等式 jiwjiwjiwjiw jjii 6 北京賽區(qū) 2004 年 ACM 比賽試題 2006 年全國信息學(xué)冬令營講座 7 蝸牛從根結(jié)點 1 出發(fā)開始尋找它的房子 它的房子可能遺失在 2 4 5 在結(jié)點 3 上住著一只蟲子 它會告訴蝸牛 以 3 為根的子樹上是否有蝸牛的房 子 蝸牛有兩種走法 蝸?？梢韵仍L問 2 如果它在那兒不能找到房子 那么 它要回到根結(jié)點 1 再通過 3 來訪問結(jié)點 4 或 5 如果還是不能找到它的房 子 那么它又要回到結(jié)點 3 再去訪問結(jié)點 5 或 4 在這種走法中 當房子 分別位于 2 4 5 的時候 蝸牛需要走的步數(shù)分別是 1 4 6 期望值是 1 4 6 3 11 3 顯然 這種走法沒有充分發(fā)揮蟲子在這里起到的作用 在另一 種走法中 蝸牛先訪問結(jié)點 3 它可以從住在 3 上的蟲子那里得知它的房子是 否存在于 4 或 5 的信息 在這種走法中 當房子分別位于 2 4 5 的時候 蝸 牛需要走的步數(shù)分別是 3 2 4 期望值是 3 2 4 3 3 這種走法合理的利用 了蟲子提供的信息 得到了更優(yōu)的數(shù)學(xué)期望值 算法分析 算法分析 不難分析出本題的大體模型是用樹的動態(tài)規(guī)劃來求解 用 Fa i 表示蝸牛的 House 在 i 為根的子樹上的期望和 用 Fb i 表示蝸牛的 House 不在 i 為根的子 樹上的時候遍歷該子樹需要的時間 用 Leaves i 表示 i 為根的子樹上葉子節(jié)點 的數(shù)目 問題的解答就是 Fa 根結(jié)點 Leaves 根結(jié)點 如果結(jié)點 u 有 k 個兒子 我們按照 S 1 S k 進行訪問 Fa u 的計算方式是 Fa u 0 Fb u 0 for i 1 to k do begin Fa u Fa u Fb u 1 Leaves S i Fa S i 2006 年全國信息學(xué)冬令營講座 8 Fb u Fb u Fb S i 2 end 用公式的形式可以表示為 k i i j iij SFaSLeavesSFbuFa 1 1 1 1 2 現(xiàn)在的問題就是如何決定訪問兒子的順序 不同的訪問順序會產(chǎn)生不同的 Fa u 我們要使得 Fa u 盡量的小 一種直觀的方法是 k 枚舉訪問順序 總體復(fù)雜度是 O nk 實在是很低 效 用狀態(tài)壓縮的動態(tài)規(guī)劃進行二次動規(guī)的話 可以將復(fù)雜度降為 O n2kk 勉 強可以接受了 注 由于狀態(tài)壓縮的動態(tài)規(guī)劃不是本文的重點 故這里不做展 開 但是我們的研究并沒有因此停止 我們嘗試用貪心的思想來分析問題 考慮一種訪問順序中的兩個相鄰元素 v 和 v 1 如果交換 v 和 v 1 之后得到的值不如交換前的值 那么 v 一定在 v 1 的前面了 具體證明如下 我們對公式 來進行一些處理 2 1 1 111 i k i i j j k i i k i i SLeavesSFbSLeavesSFa 可以看出 交換 v 和 v 1 之后 對和是不會產(chǎn)生 k i SiFa 1 k i SiLeaves 1 任何影響的 關(guān)鍵是看是增大了還是減小了 k i i j SiLeavesSjFb 1 1 1 2 把交換前和交換后的值做差 2 2 11vvvv SLeavesSFbSLeavesSFbuFauFa 最后得到的則只跟元 2 2 11vvvv SLeavesSFbSLeavesSFb 素 v 和 v 1 的信息有關(guān) 于別的元素的排列情況無關(guān) 所以元素v和v 1 是可 比的 證畢 另外 根據(jù)這個結(jié)果 可以得出另一個結(jié)論 如果 A 一定放在 B 前 B 一 定放在 C 前 可以推導(dǎo)出 A 一定放在 C 前 證明 2006 年全國信息學(xué)冬令營講座 9 2 2 2 2 BCCB ABBA SLeavesSFbSLeavesSFb SLeavesSFbSLeavesSFb 兩式相乘得到 2 2 ACCA SLeavesSFbSLeavesSFb 證畢 上面這個結(jié)論說明 本題中的 可比性 是可以傳遞的 因此可以根據(jù)這 個性質(zhì)確定出一個全序關(guān)系 因而省去了枚舉排列的部分 只需要對所有元素 進行一次排序即可 時間復(fù)雜度為 O nklog2k 非常優(yōu)秀 本題小結(jié) 本題小結(jié) 從原始的動態(tài)規(guī)劃模型入手 分析出算法的大體框架 巧妙的運用貪心思 想來除去原始算法中的冗余 進而達到優(yōu)化算法的目的 4 4 貪心思想在動態(tài)規(guī)劃中的應(yīng)用總結(jié) 貪心思想在動態(tài)規(guī)劃中的應(yīng)用總結(jié) 本文通過四個例題簡單的介紹了貪心思想在動態(tài)規(guī)劃中的兩種簡單應(yīng)用 確立狀態(tài)確立狀態(tài)和優(yōu)化算法優(yōu)化算法 貪心思想運用于動態(tài)規(guī)劃時的奇妙之處在于它合理的 利用了問題中隱含的一些特殊信息特殊信息 因而可以使得看似不能動態(tài)規(guī)劃的題目確 立出動態(tài)規(guī)劃的狀態(tài) 或者除去算法中的冗余 提高動態(tài)規(guī)劃的效率 貪婪的動態(tài)規(guī)劃 并不是一種算法 而是一種思想 要靈活的在動態(tài)規(guī) 劃中運用好貪心思想 關(guān)鍵是在于對問題的深入理解和推敲 這要求我們具備 勇于探索 大膽創(chuàng)新 舉一反三 的能力 感謝感謝 NOI2005NOI2005 浙江代表隊全體成員的支持浙江代表隊全體成員的支持 浙江省紹興縣柯橋中學(xué)吳建峰老師的技術(shù)指導(dǎo)浙江省紹興縣柯橋中學(xué)吳建峰老師的技術(shù)指導(dǎo) 參考文獻參考文獻 1 1 劉汝佳 黃亮劉汝佳 黃亮 算法藝術(shù)與信息學(xué)競賽算法藝術(shù)與信息學(xué)競賽 2 2 美美 Zbigniew Zbigniew MichalewiczMichalewicz DavidDavid B Fogel B Fogel 如何解決問題如何解決問題 現(xiàn)代啟發(fā)式方法現(xiàn)代啟發(fā)式方法 2006 年全國信息學(xué)冬令營講座 10 3 IOI2001 3 IOI2001 集訓(xùn)隊論文集訓(xùn)隊論文 動態(tài)規(guī)劃算法的優(yōu)化技巧動態(tài)規(guī)劃算法的優(yōu)化技巧 毛子青毛子青 附錄附錄 參考程序參考程序 例題二 參考程序 Horse pas 例題四 參考程序 House pas 例二原題例二原題 Tian Ji The Horse Racing Description Here is a famous story in Chinese history That was about 2300 years ago General Tian Ji was a high official in the country Qi He likes to play horse racing with the king and others Both of Tian and the king have three horses in different classes namely regular plus and super The rule is to have three rounds in a match each of the horses must be used in one round The winner of a single round takes two hundred silver dollars from the loser Being the most powerful man in the country the king has so nice horses that in each class his horse is better than Tian s As a result each time the king takes six hundred silver dollars from Tian Tian Ji was not happy about that until he met Sun Bin one of the most famous generals in Chinese history Using a little trick due to Sun Tian Ji brought home two hundred silver dollars and such a grace in the next match It was a rather simple trick Using his regular class horse race against the super class from the king they will certainly lose that round But then his plus beat the king s regular and his super beat the king s plus What a simple trick And how do you think of Tian Ji the high ranked official in China 2006 年全國信息學(xué)冬令營講座 11 Were Tian Ji lives in nowadays he will certainly laugh at himself Even more were he sitting in the ACM contest right now he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph Draw Tian s horses on one side and the king s horses on the other Whenever one of Tian s horses can beat one from the king we draw an edge between them meaning we wish to establish this pair Then the problem of winning as many rounds as possible is just to find the maximum matching in this graph If there are ties the problem becomes more complicated he needs to assign weights 0 1 or 1 to all the possible edges and find a maximum weighted perfect matching However the horse racing problem is a very special case of bipartite matching The graph is decided by the speed of the horses a vertex of higher speed always beat a vertex of lower speed In this case the weighted bipartite matching algorithm is a too advanced tool to deal with the problem In this problem you are asked to write a program to solve this special case of matching problem InputInput The input consists of up to 50 test cases Each case starts with a positive integer n n 1000 on the first line which is the number of horses on each side The next n integers on the second line are the speeds of Tian s horses Then the next n integers on the third line are the speeds of the king s horses The input ends with a line that has a single 0 after the last test case OutputOutput For each input case output a line containing a single number which is the maximum money Tian Ji will get in silver dollars SampleSample InputInput 3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0 SampleSample OutputOutput 2006 年全國信息學(xué)冬令營講座 12 200 0 0 例四原題例四原題 The Lost House DescriptionDescription One day a snail climbed up to a big tree and finally came to the end of a branch What a different feeling to look down from such a high place he had never been to before However he was very tired due to the long time of climbing and fell asleep An unbelievable thing happened when he woke up he found himself lying in a meadow and his house originally on his back disappeared Immediately he realized that he fell off the branch when he was sleeping He was sure that his house must still be on the branch he had been sleeping on The snail began to climb the tree again since he could not live without his house When reaching the first fork of the tree he sadly found that he could not remember the route that he climbed before In order to find his lovely house the snail decided to go to the end of every branch It was dangerous to walk without the protection of the house so he wished to search the tree in the best way Fortunately there lived many warm hearted worms in the tree that could accurately tell the snail whether he had ever passed their places or not before he fell off Now our job is to help the snail We pay most of our attention to two parts of the tree the forks of the branches and the ends of the branches which we call them key points because key events always happen there such as choosing a path getting the help from a worm and arriving at the house he is searching for Assume all worms live at key points and all the branches between two neighboring key points have the same distance of 1 The snail is now at the first fork of the tree Our purpose is to find a proper route along which he can find his house as soon as possible through the analysis of the structure of the tree and the locations of the worms The only restriction on the route is that he must not go down from a fork until he has reached all the ends grown from this fork The house may be left at the end of any branches in an equal probability We focus on the mathematical expectation of the distance the snail has to cover before arriving his house We wish the value to be as small as possible 2006 年全國信息學(xué)冬令營講座 13 As illustrated in Figure 1 the snail is at the key point 1 and his house is at a certain point among 2 4 and 5 A worm lives at point 3 who can tell the snail whether his house is at one of point 4 and 5 or not Therefore the snail can choose two strategies He can go to point 2 first If he cannot find the house there he should go back to point 1 and then reaches point 4 or 5 by point 3 If still not he has to return point 3 then go to point 5 or 4 where he will undoubtedly find his house In this choice the snail covers distances of 1 4 6 corresponding to the circumstances under which the house is located at point 2 4 or 5 5 or 4 respectively So the expectation value is 1 4 6 3 11 3 Obviously this strategy does not make full use of the information from the worm If the snail goes to point 3 and gets useful information from the worm first and then chooses to go back to point 1 then towards point 2 or go to point 4 or 5 to take his chance the distances he covers will be 2 3 4 corresponding to the different locations of the house In such a strategy the mathematical expectation will be 2 3 4 3 3 and it is the very route along which the snail should search the tree InputInput The in