文稿教程排列_第1頁
文稿教程排列_第2頁
文稿教程排列_第3頁
文稿教程排列_第4頁
文稿教程排列_第5頁
已閱讀5頁，還剩14頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、Pal試題討論 清華大學 莫濤問題描述給定整數n A B對于一個1 n的全排列X，若整數對(Xi, Xj)滿足i j且Xi =our_ans，得10分。否則得分為非最優解最多得7分當your_ansour_ans*0.7時只有1分得分情況集訓隊：周而進 88周奕超 67吳尚 蔣中天 62非集訓隊：福建 林洋 65吉林 趙志恒 61北京 張放 56試題討論整體思路題目特點數據規模約束很強最多903種數據部分分N越大，A越大，B越小，越困難打表搜索，動態規劃，貪心，隨機化多種算法結合模型抽象轉換為圖論模型，一個數字用一個結點表示若數字 p 必須在數字 q 前面(即 p = A + q 或 p =

2、B * q)，則由結點 p 向結點 q 連一條邊可行的序列對應有向無環圖的拓撲序列例 n=6, A=2, B=2可行序列5 6 3 4 2 16 4 5 3 2 1123456改變權和計算方式令Fi表示Xi前面比Xi小的數的個數則Ans= XjXi = Xi*(Fi(NXi(i1Fi) =(Xi*i) N(N+1)(N+2)/6只需最大化Xi*i算法一狀態壓縮動態規劃F L1, L2, , LA表示當前第 i 條鏈取到第 Li 個數時的最大權和，枚舉下一個取的數來轉移可以解決A較小情況期望得分：20分算法二貪心B=1時，該圖只有若干條鏈。結論：每條鏈在最優排列中必然是連續的，且平均值較小的鏈在

3、前。期望得分：10分算法三搜索搜索順序：優先權值較小的點，以得到較優的答案最優化剪枝：去掉剩余的拓撲圖中鏈之間的邊，利用貪心算法計算剩下的圖能得到的權和的上界，若當前權和加上上界不能優于當前的最優答案，則可以剪枝期望得分：10分幾個重要結論結論一：若已知某幾個數在最優排列中連續，則可以將它們等價為一個數，大小為它們的平均值。結論二：若最小數可選則立即選擇。結論三：若選擇某點時其后繼點可選，則立即選擇其某個后繼點。上述結論均可用調整法證明。優化算法直接利用結論二與結論三算法一+優化：4050分算法三+優化：2030分一個錯誤猜想猜想：若剩下的子圖是若干不連通的部分，則對每個子圖分別求最優解，再利用算法二合并。反例：（1,4） +（2）=（1,2,4）子圖的最優解不滿足從大到小的順序算法一+優化+猜想：7080分標程，改進的合并算法子問題：給定若干條鏈，將其合并使權和最大。根據結論，每次選出平均值最小的塊，將其與前驅合并，若已經是鏈首，則加入最終排列。仍不一定正確，連通塊的最優排列對于全局不一定最優。但幾乎可以求出最優解。數據25，塊之間的邊較少，易分為若干子圖。一個強有力的剪枝每條鏈的任意前綴在加上它往前任意多個這個前綴不依賴的數后，平均值不變大。搜索+優化+剪枝：608

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論