文稿教程排列

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

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

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