文稿教程排列

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

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

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