文稿教程排列

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

2、B * q)，則由結(jié)點 p 向結(jié)點 q 連一條邊可行的序列對應(yīng)有向無環(huán)圖的拓撲序列例 n=6, A=2, B=2可行序列5 6 3 4 2 16 4 5 3 2 1123456改變權(quán)和計算方式令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表示當(dāng)前第 i 條鏈取到第 Li 個數(shù)時的最大權(quán)和，枚舉下一個取的數(shù)來轉(zhuǎn)移可以解決A較小情況期望得分：20分算法二貪心B=1時，該圖只有若干條鏈。結(jié)論：每條鏈在最優(yōu)排列中必然是連續(xù)的，且平均值較小的鏈在

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