2023學(xué)年完整公開課版例題選講

2005年浙江省隊培訓(xùn)

第4講題目選講劉汝佳例題:最大子矩陣給n*n矩陣，求和最大的子矩陣分析枚舉起、止行號r1和r2，壓縮子矩形成為一行，變成一維問題,第i個元素為b[i]=a[r1,i]+a[r1+1,i]+…+a[r2,i]對于第i列,計算前綴和prefixi[j]=a[1,i]+a[2,i]+…+a[j,i]則b[i]=prefixi[r2]-prefixi[r1-1],常數(shù)時間計算前綴和:O(n2),一維問題:O(n)共O(n3)思考:最大環(huán)形子矩形給n*n矩陣,第一行和最后一行看作是連通的;第一列和最后一列看作是連通的求和最大的子矩陣例題:密度圖給出n>r>0，一個n*n矩陣F，矩陣中距離定義為兩個格子的行坐標(biāo)差和列坐標(biāo)差中較大的一個求出矩陣W，其中w[i,j]為F矩陣中到(i,j)距離不超過r的所有數(shù)的和分析方法一：N=5,r=1時考慮W(3,3)和W(3,4)的關(guān)系。需要計算一列上連續(xù)的一段和，同樣可以遞推得到方法二：d[i,j]為從左上角到(i,j)的矩形內(nèi)所有數(shù)的和例題:方格給一些長度為1的線格式:(x,y,D),其中D可以是H(往右)或者V(往下)數(shù)各個大小的正方形的個數(shù)。分析算法一:用01矩陣表示每條邊是否存在.枚舉左上角和右下角O(n4),檢查四條邊是否完全填充O(n),共O(n5)算法二:預(yù)處理:每個點往右最大長度為幾,從右往左遞推d[i]=d[i+1]+1,或d[i]=0,預(yù)處理O(n2)算法一降為O(n4)例題:城市正視圖求正南視圖中,哪些建筑物是可見的下圖從左到右依次為5,9,4,3,10,2,1,14可見分析只需要判斷南墻,即每個建筑物變成矩形預(yù)處理從北到南排序所有南墻,依次考慮水平、豎直離散化主算法每次更新每個元線段的墻集合,從低到高掃描每個元線段上每個高度最多進/出集合一次,因此每個元線段的維護只需要O(n)一共有n條元線段,因此為O(n2)思考:邊界給出從X，Y出發(fā)的路線（N，E，W，S），找出邊界。Bugs公司Bugs公司生產(chǎn)一種2×3單位尺寸的高科技芯片嵌入N×M（N≤150,M≤10）單位尺寸的模板內(nèi)，損壞的單位小方格已被標(biāo)上黑色記號芯片內(nèi)不能有黑色記號，同時芯片與芯片不能重疊。將盡量多的芯片嵌入模板分析M<=10,可以考慮信息壓縮的動態(tài)規(guī)劃定義基線B[i,j]為前i-1列和第i列前j行組成的圖形,若從右往左從下往上處理,則B[i,j]為考慮格子(i,j)時的剩余棋盤分析剩余棋盤B[i,j]上能切下多少芯片要取決于B[i,j]已經(jīng)有哪些格子被占用了用(0,2,1,0,2)表示每行已經(jīng)被占了幾個格子(注意:如果占了左邊的格子,右邊也不能用)分析把占用情況看成3進制數(shù),則有3M種情況設(shè)d[i,j,P]為B[i,j]的占用情況為P時最多能嵌入的芯片數(shù),轉(zhuǎn)移方式:忽略;放2*3;放3*2.下圖為處理到深灰色格時選擇放置3*2分析狀態(tài)有MN3M個,轉(zhuǎn)移為O(1)的,總時間復(fù)雜度為O(MN3M)空間復(fù)雜度為O(MN3M),但可以用滾動數(shù)組優(yōu)化,即只保存相鄰三列的占用情況，降為O(M3M)，可以承受優(yōu)化:很多P是不可能出現(xiàn)的,因為只有2*3和3*2兩種芯片,無法產(chǎn)生單獨的一列占用最近公共祖先(LCA)給一棵樹T設(shè)計在線算法,對于詢問(u,v),回答u和v的最近公共祖先算法一算法一:O(nlogn)-O(log2n)預(yù)處理DFS求出每個結(jié)點的level.O(n)遞推得每個結(jié)點的2i級直接祖先,O(nlogn)詢問二分LCA的層次每次用倍增法求該層次上的父親詢問是O(log2n)的算法二算法二:DFS求Euler序列,即E[1…2n-1],設(shè)R[i]為i第一次出現(xiàn)的下標(biāo),L[i]為E[i]的深度,則LCA轉(zhuǎn)化為RMQ,存在O(nlogn)-O(1)算法若R[u]<R[v],LCA(T,u,v)=RMQ(L,R[u],R[v])若R[u]>R[v],LCA(T,u,v)=RMQ(L,R[v],R[u])算法三算法三:注意到L滿足±1性質(zhì)把A劃分成每部分為L=log2n/2的小塊一共有2n/log2n塊用O(n)求出每個小塊的最小值A(chǔ)’[i]A’上的RMQ預(yù)處理:O(n),詢問O(1)問題轉(zhuǎn)化為詢問In-RMQ(x,a,b),即第x個塊的第a個元素到第b個元素的最小值算法三(續(xù))問題轉(zhuǎn)化為詢問In-RMQ(x,a,b),即第x個塊的第a個元素到第b個元素的最小值最多只有2L=n1/2種本質(zhì)不同的數(shù)組最多只有L2=log2n/4種不同的詢問完全遞推,在O(n1/2log2n)的時間完成,則In-RMQ是簡單的查表工作,是O(1)的算法三是O(n)-O(1)的離線算法快速離線算法(Tarjan):L(u)<=L(v)時,根據(jù)LCA(u,v)把結(jié)點分成等價類u的子樹上結(jié)點v:LCA(u,v)=uu兄弟的子樹上的結(jié)點v:LCA(u,v)=f[u]u的”叔叔”(父親的兄弟)的子樹結(jié)點v:LCA(u,v)=f[f[u]]所有結(jié)點初始為WHITE,對于所有詢問LCA(u,v),把v保存在集合Q[u]中voidLCA(u){MAKE-SET(u);ancestor[FIND-SET(u)]=u;forv=everysonofu{LCA(v);UNION(u,v);ancestor[FIND-SET(u)]=u;}color[u]=BLACK;forv=everyelementinQ[u]{if(color[v]==BLACK)ans[u,v]=ancestor[FIND-SET(v)];}}例題:電子表格計算器給出一個表格,有些格子已知道,有些需要計算.行用A,B,C…表示,列用0,1,2…表示計算出所有值,或報告出現(xiàn)循環(huán)引用A1+B153B0-A1353-2分析方法一:不斷計算可以算出來的元素,直到無元素可算.迭代次數(shù)不超過O(nm),每次需要檢查nm元素,每次檢查最多需要O(nm)次計算(如果式子長),共O(n3m3)方法二:先拓撲排序,按照拓撲順序計算.拓撲排序為O(n2m2),計算nm次,每次O(nm),共O(n2m2)例題:間諜每兩個城市只有一條路你需要為兩個間諜安排安全會議，規(guī)則如下：間諜在白天移動，在晚上開會；間諜應(yīng)該每天改變他所處的位置；間諜僅能沿著連接城市的路旅行間諜在一天之內(nèi)不能旅行超過到一個鄰城的距離。間諜早上出發(fā)在晚上之前可到任一相鄰城市如果兩個間諜在同一天晚上到達一個城市，那么這樣一個會議就能開尋找最早能開會的時間分析(x,y)為兩個間諜分別在城市x和y，則第二天的情況有d[x]*d[y]種，其中d[x]為x的度數(shù)總邊數(shù)為sum{d[x]*d[y]}=O(n3)，用BFS找最短路，則時間復(fù)雜度為O(n3)。例題:矩形在平面上畫了N個長方形，每個長方形的邊平行于坐標(biāo)軸并且頂點坐標(biāo)為整數(shù)。我們以以下方式定義印版：每個長方形是一個印版；如果兩個印版有公共的邊，那么它們組成新的印版，否則這些印版是分離的。左圖有兩個，右圖只有一個分析把矩形看作點，有公共邊的矩形連邊，問題轉(zhuǎn)化為求連通分量的個數(shù)判斷方法：例題:位圖有一個尺寸為n*m的長方形位圖，位圖的每個像素是白色或者是黑色但是至少有一個是白色，第i行j列的像素被稱作像素(i,j)。每兩個像素(i1,j1)和(i2,j2)的距離定義成：|i1-i2|+|j1-j2|對每個像素，計算到最近的白像素的距離分析如果對于每個黑像素進行floodfill，將是O(n2m2)初始隊列里有所有白像素，這樣的floodfill可以一次算出所有黑像素的距離P-折線兩端都在整點上的水平或豎直線段稱為P線段如果一根折線由K個P線段組成，在這些P線段中每兩個相鄰線段垂直的，我們稱其為度為K的P折線給定一些P線段和兩個整點A和B，尋求連接A和B并且不與任何給定P線段相交的P折線。如果存在，求其中度最小的一條，如果不存在，輸出無解分析坐標(biāo)離散化對于每條線段，在四周距離為1處構(gòu)造上下左右四條直線，交點共O(n2)個每次決策（沿同一方向走的格子數(shù)）為O(n)個，共O(n3)分析可以以(x,y,d)為狀態(tài)，則到四個子狀態(tài)的距離為0或者1，先擴展為0的，共O(n2)在此狀態(tài)下也可以用O(n)個決策的方法，一旦此方向上有一個被檢查，則停止，仍然O(n2)矩形里的暴風(fēng)雨M*N的網(wǎng)格，每個格子上有一個字母，相同字母組成連通塊稱為省。字母A所在的省稱為首都，且一定不包含邊界格子.任何一個2*2矩陣的四個格子不可能分屬四個不同的省.兩個省如果分別有兩個格子X,Y且X與Y相鄰，則稱這兩個省相鄰。占領(lǐng)一個省需要滿足以下任一個條件這個省包含邊界格子這個省和某個已經(jīng)被占領(lǐng)的省相鄰?，F(xiàn)在要求把所有與首都相鄰的省都占領(lǐng)，問至少要占領(lǐng)多少個省分析任意一個“田”中4個格子不能分屬4個省份。初看似乎沒什么用，但他是一個很重要的條件。因為利用這個條件可以證明：與首都相鄰的省份（這些是必須被占領(lǐng)的）都是直接或間接的連通的。因此可以把這些省份縮成一個點S，添加一個源點T與所有的邊界省份相連，問題轉(zhuǎn)化為求S到T的最短路。例題:積水一個長方形網(wǎng)格包含了n*m塊地，每塊地上面有1個長方體。每一個長方形蓋住了一塊地，地的面積是1平方英寸。相鄰的地上的長方體之間沒有空隙。一場大雨降臨了這個建筑物，在建筑物的某些區(qū)域有積水產(chǎn)生。給各方格高度,求積水總量分析定義每塊地上的長方體的高度稱為原始高度積滿水時的水面高度稱為積水高度（高于積水高度的水一定會流走，低于積水高度的水一定流不走）積水高度與原始高度之差為積水深度如果一個長方體上不可能有積水，那么它的積水高度就等于它的原始高度。最外圈不能積水，積水高度等于原始高度分析算法一:由外而內(nèi)計算。每次選取外圍的格子中積水高度最低的一個格子x，考慮它周圍所有在網(wǎng)格內(nèi)部的格子y想象不斷的往x和y里注水，但是x的積水高度固定（想象該高度處有一個小孔），因此如果y的原始高度不小于x的積水高度，那么它的積水高度就是它的原始高度如果y的原始高度小于x的積水高度，那么它的積水高度就等于x的積水高度每次用堆取出x進行計算，O(mnlogmn)。分析算法二：每個積水塊的高度相等，積水塊之間的“干地”沒有積水首先“往上”寬搜得到最外面積水塊A外的輪廓，它是最外層的干地輪廓中最低的高度為塊A的積水高度h“往下”寬搜得到塊A，每個格子的高度都賦為h，同時得到下一個塊的輪廓例題:RGB平面上有N條線段（頂點坐標(biāo)范圍在0~32000），這些線段都被染成R、G、B三色之一。X軸上的每一點，被染成了Y值與之相同的，最近的線段上的點的顏色。求X軸上R、G、B三種顏色的總長度。算法一把所有的端點、交點的x坐標(biāo)拎出來，離散并刪除重復(fù)。對于每一個離散列，找到所有的線段，并找到距離坐標(biāo)軸最近的一個。時間復(fù)雜度為O(N3)。算法二先把交點排序,這一步是O(N2logN)的從左到右依次處理每一個離散列，將線段按照當(dāng)前列中的出現(xiàn)，從下至上排序。遇到一個交點，就交換兩條線段的位置；遇到一個端點，就進行插入或刪除。總時間復(fù)雜度O(N2)即可完成這個“順序”的維護，對每個離散列，只需要選取最下面的一條線段的顏色即可。算法三枚舉一條線段L，看它有多少長度能夠照射到X軸上，也就是球它有多少部分被其他線段遮住了，枚舉線段L’,求出它遮住L的區(qū)間，然后把所有區(qū)間合并就求出了遮住部分的長度，然后把照射到x軸上的長度加到L的顏色中每次有n個區(qū)間,排序需要O(nlogn),共O(n2logn)例題:方格紙有一張N×N的白格子紙，按順序?qū)個矩形（與紙張邊緣平行）范圍內(nèi)的格子染上黑色或白色，后染上的顏色可以覆蓋先染上的顏色。求最后紙上有多少白格子。分析首先可以進行離散化（不一定有必要，因為坐標(biāo)都是整點，在范圍1~N內(nèi)）接下來逐行處理，容易想到N2M的算法算法一用c表示顏色,b表示是否已經(jīng)被覆蓋初始c全為白色，b均為false從最后一個矩形開始，譬如說要覆蓋該行的x~y，那么對x≤i≤y，如果b[i]為false，將c[i]置為相應(yīng)的顏色，b[i]修改為true。每處理一個矩形需要O(N)的時間,因此為O(NM),所有行一共O(N2M)算法二如果每次都是成功染色,則為O(N2+M)設(shè)置next數(shù)組避免空循環(huán)而無法染色的情況初始時候設(shè)定next[i]=i+1，譬如覆蓋3~5，不僅修改b[3..5]和c[3..5]適當(dāng)修改，還需要將next[3..5]置為6，接下來覆蓋2~7，那么先處理b[2]和c[2]，這時候發(fā)現(xiàn)b[3]為真，那么直接走到next[3]=6，接著覆蓋6~7,且next[2],next[6~7]修改為8。這個過程有些類似于并查集，甚至還可以考慮“路徑壓縮”，可以證明時間復(fù)雜度為線性。決斗編號為1~n的n個人按逆時針方向排成一圈，他們要決斗n-1場。每場比賽在某相鄰兩人間進行，敗者退出圈子，緊靠敗者右邊的人成為與勝者直接相鄰的人。任意兩人之間決斗的勝負都將在一矩陣中給出（如果A[i,j]=1則i與j決斗i總是贏，如果A[i,j]=0則i與j決斗時i總是輸），求出所有可能贏得整場決斗的人的序號分析d[i,j]表示是否有可能i和j相遇,則第i個人能取得最后的勝利當(dāng)且僅當(dāng)d[i,i]為true狀態(tài)轉(zhuǎn)移:考慮相遇前的最后一步,則d[I,j]為true當(dāng)且僅當(dāng)能找到一個k,使得i能遇k,k能遇到j(luò),且i或者j能打敗k狀態(tài)有O(n2)個,轉(zhuǎn)移有O(n)個,共O(n3)佳佳的筷子中國人吃飯喜歡用筷子。佳佳與常人不同，他的一雙筷子有三只，一雙短筷子加上一根比較長的（一般用來穿香腸之類的食物）。兩只較短的筷子的長度應(yīng)該盡可能接近，但是最長的那根長度是無所謂的。如果一雙筷子的長度分別是A，B，C(A≤B≤C)，則用(A-B)2的值表示這雙筷子的質(zhì)量，這個值越小，這雙筷子的質(zhì)量越高。佳佳請朋友吃飯，并準備為每人準備一雙這種特殊的筷子。佳佳有N（N≤5000）只筷子，他希望找到一種辦法搭配好K雙筷子，使得這些筷子的質(zhì)量值和最小分析任一副筷子中A和B一定長度相鄰.證明如下對于某副筷子（A1,B1,C1）和另一副筷子（A2,B2,C2），如果A1<=A2<=B1<=B2，那么交換一下筷子重新組合成（A1,A2,C1）和（B1,B2,C2）質(zhì)量和會更優(yōu)。對于某副筷子（A,B,C）和閑置的筷子D，如果A<=D<=B，那么交換一下重新組合成（A,D,C）質(zhì)量和也會更優(yōu)。我得到了一個線性結(jié)構(gòu)。遞推之前，首先將N只筷子從小到大排序，Li是第i只筷子的長度分析用d[i,j]表示用i到n的筷子組成j副筷子的最小質(zhì)量值之和，則當(dāng)且僅當(dāng)n-i+1>=3j的時候狀態(tài)是合法的。狀態(tài)轉(zhuǎn)移方程為時間復(fù)雜度為(NK)偷懶的工人人們都說A公司的工人很勤勞，因為只要一有可以做的工作，他們馬上就會去做，而不會出現(xiàn)有任務(wù)可以完成，但他卻閑著沒事干的情況。雖然話說得沒錯（因為公司有這個規(guī)定），但是工人們實際上是很懶的，他們希望在符合公司規(guī)定的前提下讓自己的工作時間盡量短。假設(shè)某工人有n個任務(wù)要做，第i個任務(wù)恰好需要ti單位的時間才能完成，而且必須在時間區(qū)間[ai,di]被執(zhí)行（即任務(wù)的開始時刻不小于ai，結(jié)束時刻不大于di,t≤di-ai<2ti）。假設(shè)該工作在同一時間只能進行同一個任務(wù)，而同一個任務(wù)要么不做，要么在規(guī)定的期限內(nèi)不間斷的做。他應(yīng)該怎樣選擇任務(wù)，才能讓自己的工作時間盡量少呢？分析如果用d[i]代表i時刻以后還需要工作的最少時間，如何狀態(tài)轉(zhuǎn)移?我們不知道哪些任務(wù)是已經(jīng)完成了的（因為它們執(zhí)行時間不確定），因此決策集合無法確定好在有條件t<=di-ai<2ti。當(dāng)完成一個任務(wù)以后，嚴格的時間期限已經(jīng)不可能允許工作再重復(fù)選擇這個任務(wù)了,因此i可以唯一確定可以進行的任務(wù)集合分析如果用d[i]代表i時刻以后還需要工作的最少時間,Ti表示此時刻可以進行的工作集合,則狀態(tài)轉(zhuǎn)移有兩類Ti為空:等于d[i+1]Ti不為空:對Ti中的任務(wù)j,取min{d[i+tj]+tj}用記憶化搜索可以避免無意義的遞推計算平坦的虛線有一個畫在一張紙上的坐標(biāo)系。考慮用一只鉛筆從紙的左邊到右邊所畫的折線。要求線的每個轉(zhuǎn)折部分包含的轉(zhuǎn)折部分直線與OX軸的夾角屬于[-45,45]，滿足上述條件的折線稱之為flatbrokenlines。假設(shè)給出具有整數(shù)坐標(biāo)的N個不同點，那么為了覆蓋所有這些點需要flatbrokenlines的最小值（如果某點屬于這條線，則說該點被覆蓋）。平坦的虛線例如：給出了6個點，其坐標(biāo)分別為(1,6),(10,8),(1,5),(2,20),(4,4),(6,2)覆蓋它們最少的flatbrokenlines是3分析逆時針旋轉(zhuǎn)45度，則每個點只能在前一點的右上方算法一：維護高度集合H，每個元素h代表一條flatbrokenlines。按照x從小到大排序，x相同按y從小到大排序如果H內(nèi)元素都比y大，只能增加一個line，即y加入到H中，否則選擇在H中選擇小于y且最接近y的高度，變?yōu)閥實現(xiàn)：二分查找。不需要BST分析算法二：定義偏序關(guān)系i<ji在j左下方，則由Dilworth定理知答案（最大鏈覆蓋）等于最長反鏈長度按x從小到大排序，則最長反鏈為關(guān)于y的最長下降子序列，用O(nlogn)輕松完成快樂的蜜月賓館有一間蜜月房非常舒適,經(jīng)理在每年年底都會收到第二年的所有蜜月房預(yù)訂單。第i中預(yù)訂單包括：到達日期Si、離去日期Ti和費用Ci不與任何其他預(yù)訂要求發(fā)生沖突的預(yù)訂單必然會被接受;對于其他訂單,任兩份的時間都不能重疊你的任務(wù)是在所有合法方案中找出獲利第k(k<=100)大的方案.當(dāng)然，可能有若干種方案的獲利是一樣大的。假如有3種方案的收入同時為3，有2種方案的收入為2，則收入為3的方案都屬于獲利最大，收入為2的方案都屬于獲利第二大。所有的住、離店登記都在中午12點進行。共有r個預(yù)訂要求(r≤20,000)分析首先考慮k=1的情況.由于天數(shù)比較小(最多366天),因此設(shè)d[i]為前i天可到達的最大收益,Si為右端點在i的線段集.有兩類轉(zhuǎn)移不選取Si的任何線段,為d[i-1]選取某條左端點為j,權(quán)值為w的線段,為d[j]+w時間復(fù)雜度為O(D+r),因為所有訂單恰好被考慮一次,其中D為一年的天數(shù)分析前i天收益前k大的方案,前j天(j<i)天也是前k大的,因此每個階段需要保留前k大的方案設(shè)d[i,k]為前i天第k大的方案,每次考慮某條左端點為j的線段x時,設(shè)數(shù)組g[k]=d[j,k]+w,與d[i,k]歸并取前k的元素每考慮一條線段的時間復(fù)雜度為O(k),因此總時間復(fù)雜度為O(D+kr)移動機器人在二維網(wǎng)格上有許多機器人。每個機器人的狀態(tài)由(x,y,d)表示,即位置和朝向(東南西北).每個機器人按照各自固定的指令執(zhí)行移動,兩個機器人互不影響，同一個位置可以有多個機器人。指令有兩種,轉(zhuǎn)身(左轉(zhuǎn)90，180或270度)和移動(按當(dāng)前朝向移動一個單位)在機器人開始移動前，可以去掉一些指令，改變機器人的行動路線和最終位置。刪除最少的指令讓所有機器人到達同一個最終位置指令數(shù)不超過50分析首先求出每個機器人能到達的范圍和每個點需要刪除的最少指令分析每個機器人的指令數(shù)目不大于50，這就將機器人活動的范圍限制以初始位置為中心，邊長為50的正方形中。機器人的位移用二元組(x,y)(-50≤x,y≤50)表示，方向合起來表示一個狀態(tài)。設(shè)d[i,x,y,k]表示前i條指令執(zhí)行后到達狀態(tài)(x,y,k),需要最少刪除多少條指令用更新法做狀態(tài)轉(zhuǎn)移,決策是O(1)的(刪還是不刪),時間O(n2),R個機器人共O(Rn2)分析然后再求出最優(yōu)點.每次求交集,去掉不可能的點,同時記錄剩下點需要刪除的指令最小值,處理完所有機器人即可求交集的方法可以用增量法,逐個判斷集合i是否在前i-1個集合的交中方法一:用排序二叉樹,查找和刪除都是O(logn)的方法二:用二維數(shù)組記錄第1個機器周圍的n2個格子是否在集合中,查找和刪除都是O(1)的最終時間復(fù)雜度為O(Rn2)方塊消除n個帶顏色方格排成一列，相同顏色的方塊連成一個區(qū)域（如果兩個相鄰方塊顏色相同，則這兩個方塊屬于同一區(qū)域）游戲時，你可以任選一個區(qū)域消去。設(shè)這個區(qū)域包含的方塊數(shù)為x，則將得到x2分方塊消去之后將產(chǎn)生空列,此時其右邊的所有方塊就會向左移,直到所有方格連在一起方塊消除下面是一個游戲的例子分析輸入表示成兩個長度為L的數(shù)組color和lenL表示有多少“段”不同的顏色方塊color[i]表示第i段的顏色len[i]表示第i段的方塊長度題目的例子成color={1,2,3,1},len={1,4,3,1}用(i,j,k)表示在第i~j段方塊的右邊添加k個顏色為color[j]的方塊后得到的方塊序列,相當(dāng)于考慮第i~j段,但讓len[j]的值增加k分析d

[i,j,k]表示把序列(i,j,k)消除的最大得分考慮最后一段，有兩類決策如果馬上消掉，就是d[i,j-1,0]+(len[j]+k)2；如果和前面的若干段一起消，設(shè)這“若干段”中最后面的那一段是p(i<=p<j)，得分為d[i,p,k+len[j]]+d[p+1,j-1,0],其中color[p]=color[j]邊界條件是f[i,i-1,0]=0時間O(n4),建議用記憶化遞歸實現(xiàn)不可解碼的編碼給定n(n≤20)個01編碼串S1,S2,…,Sn，尋找一個編碼串T，至少可被分解為兩種不同的Si的排列例如：給定5個01編碼串：S1=0110，S2=00，S3=111，S4=001100，S5=110。一個符合要求的編碼串T是：001100110，兩種分解方法為00+110+0110(S2+S5+S1)001100+110(S4+S5)而0110110只有一種分解方法0110+110(S1+S5)尋找長度最短的符合要求的編碼串T，若有多個符合要求的最短編碼串T，則輸出字典順序最小的分析先考慮搜索策略。搜索的關(guān)鍵是編碼串T至少存在兩種不同的分解方法。從搜索分解方法出發(fā)，同時搜索兩種分解方法，可以大大減少搜索量。分析不完整的分解方案所無法匹配的剩余部分，一定是某個S編碼串的后綴。定義狀態(tài)d[i,j]為：當(dāng)B部分為第i個數(shù)字串從第j+1開始的后綴時，A部分的最短長度邊界:當(dāng)存在某個長度為j的串為串i的前綴時d[i,j]=j,其他d[i,j]為無窮大分析轉(zhuǎn)移和A無關(guān),只考慮B.從某個狀態(tài)d[i,j]出發(fā)進行轉(zhuǎn)移，可以分為兩種情況：某串k是B的前綴，則用d[i,j]+L[k]更新d[i,j+L[k]]B是某串k的前綴,則用d[i,j]+L[i]-j更新d[k,L[i]-j]最后的解是所有d[k,L[k]]中最小的一個分析因為題目要求找出的串是長度最短且在同長度的串中字典序最小的一個，因此，若長度不等時，可以直接取小的那個；若長度相等，則要追溯前面的狀態(tài)，取字典序較小的那個。這與一般的動態(tài)規(guī)劃是不太相同的，需要特別注意為了編程方便，可以采用記憶化搜索的方式。另外，由于程序中需要大量用到查找某個字符串是否存在的操作，為了提高程序效率，可以用Trie的結(jié)構(gòu)來存儲最優(yōu)排序二叉樹邊長為3的正三角形分成三層共9個小的正三角形，把它們從頂?shù)降?，從左到右?~9編號。邊長為n的正三角形可以劃分成n2個單位三角形。四個這樣的邊長為n的正三角形可以組成一個三棱錐。將正三棱錐的三個側(cè)面依順時針次序(從頂向底視角)編號為A,B,C，底面編號為D。右圖為展開圖，圓點為該面的頂最優(yōu)排序二叉樹把這A、B、C、D四個面各自劃分成n2個單位三角形,并把1~4n2分別填入四個面總共4n2個單位三角形中?，F(xiàn)在要求你編程求由單位三角形組成的最大排序二叉樹。對于任一單位三角形，可選它三個相鄰(有公共邊的三角形相鄰)的單位三角形中任意一個作為父結(jié)點，其余兩個分別作為左孩子和右孩子。當(dāng)然，做根結(jié)點的單位三角形不需要父結(jié)點，而左孩子和右孩子對于二叉樹中的任意結(jié)點來說并不是都必須的。最優(yōu)排序二叉樹舉例給出四面上的數(shù)如下圖則最優(yōu)排序二叉樹如右圖分析設(shè)d[i,j,k]為根是i,結(jié)點范圍為j~k時的最大排序二叉樹結(jié)點個數(shù)i有三個鄰居可以作i的子樹的根,但不在[j,k]范圍內(nèi)的結(jié)點是不能選的.考慮i所有能選的鄰居u,根據(jù)u和i的關(guān)系可唯一確定它是i的左子樹還是右子樹.狀態(tài)轉(zhuǎn)移時,取左子樹和右子樹各自的最大值并相加即可結(jié)點范圍的設(shè)立自然的排除了把父親選作兒子的情況,也避免了兩棵子樹的交叉分析狀態(tài)有三維,似乎是O(n6)的,但其中一維取決于i的父親,因此只需要記錄i的父親是它的第幾個鄰居狀態(tài)數(shù)是O(n2)的(單位三角形有4n2個),狀態(tài)轉(zhuǎn)移時間O(n2),總時間O(n4).空間也是O(n4)的提示:用記憶化搜索來實現(xiàn)本題的動態(tài)規(guī)劃可以大大降低編程復(fù)雜度機器人的名字考慮一種基于重復(fù)子串的壓縮方法用[St]k表示k個相同的子串St(其中St稱為重復(fù)子串，k是一個單字節(jié)整數(shù)，只占一個字符位置)如果這k個子串并沒有連在一起，則可以在[St]k的后面加上{S1}t1{S2}t2…{Sr}tr（1<ti<k，ti<ti+1），表示在第ti個St的后面放置Si，Si稱為插入子串St和Si也都可以是壓縮后的字符串比如I_am_WhatWhat_is_WhatWhat的壓縮結(jié)果為I_am_[What]4{_is_}2，長度為19(例子中的空格用下劃線“_”表示，數(shù)字2和4實際上是用單字節(jié)二進制表示的)名字不會以空格開始或結(jié)尾，大小寫敏感分析令d[a,b]表示以a,b為起止位置的串(記為S[a,b])的最短壓縮長度,則目標(biāo)為d[1,L]狀態(tài)轉(zhuǎn)移連接:d[a,b]=min{d[a,i]+d[i+1,b]},a<=i<b壓縮:需要確定重復(fù)子串.當(dāng)重復(fù)子串很多時,決策枚舉的代價較大壓縮決策可以通過動態(tài)規(guī)劃來枚舉!分析g[a,b,c]表示將串S[a,b],選擇長度為c的重復(fù)子串進行壓縮得到的最短長度.枚舉插入串(可能為空)的下一個位置i,狀態(tài)轉(zhuǎn)移方程為分析邊界條件d[a,b]的狀態(tài)轉(zhuǎn)移方程如何較快的判斷是否有S[a,a+c-1]=S[i,i+c-1]?從c=1開始遞推,總O(L3)分析時間:預(yù)處理O(L3),核心O(L4),共O(L4)空間g:本來是三維的O(L3)的,但注意到在每個式子里b參量沒有發(fā)生變化,故以b為階段遞推,只需要O(L2)的空間預(yù)處理結(jié)果:如果用h[a,b,c]表示是否有S[a,a+c-1]=S[b,b+c-1],則又是三維的.可以用鏈式存儲,用next[a,b]表示子串S[a,b]的下一個相同子串的開始位置,則只需要O(L2)的空間迷宮統(tǒng)計Jimmy自己辦了一個游園活動，其中一個項目是讓游客去走一個隨機生成的m行n列(1≤m≤5,1≤n≤6)的迷宮，迷宮里有空地，也有障礙物（每個障礙物恰好占一個方格）。游客總是從左上角走到右下角，每次可以往東南西北四個方向之一行走迷宮的生成方式很簡單：每一個格子都有一個獨立的概率p，表示該格子為障礙物的概率。如果程序生成了一個無解的迷宮，它會重新生成一個。你的任務(wù)是計算每個格子成為一個有解迷宮中的障礙物的概率。分析m和n都很小,是否可以隨便做呢?m=n=5時有解迷宮有1,225,194個m=5,n=6時高達30,754,544個如果把所有有解迷宮都列舉出來再計算概率，需要花費約10分鐘的時間。思路：不列舉所有有解迷宮，而是把這些迷宮分成若干個不相交的集合，在每個集合中分別計算概率分析考慮像經(jīng)典的信息壓縮動態(tài)規(guī)劃一樣,一列一列遞推需要知道當(dāng)前列（或者多列）的哪些信息?如果只是簡單的保存是否有障礙的信息,保存一列、兩列或者三列都可能不夠。如果全部保存完，就沒有意義了。怎么辦呢？分析只記錄當(dāng)前列的每個格子是否能和起點連通也是不對的，因此即使當(dāng)前某個格子和起點不連通，以后也是可能連通的。這樣做在狀態(tài)轉(zhuǎn)移的時候遇到了困難正確的做法是記錄當(dāng)前列y中每兩個格子是否連通方法一：每兩個格子用01表示，一共m2/2個格子對，共2m*m/2種狀態(tài)，太大方法二：記錄每個格子(x,y)的P[x]值，0表示它和起點連通，否則它表示同列中與該格連通的所有格子的最小行編號（如果沒有這樣的格子，則P[x]=x）。這樣狀態(tài)最多(m+1)!個，可以承受分析用S(i,P)表示共i列，最后一列的連通情況為P的所有迷宮集合為了統(tǒng)計和各個格子相關(guān)的概率，需要增加一維b，用d[i,P,b]表示S(I,P)中最后一列第b個格子為障礙的迷宮總概率,為了方便b=0表示總概率b的選擇有mn+1種,P的元素有(m+1)!個分析這樣，每次進行狀態(tài)轉(zhuǎn)移時，枚舉當(dāng)前列的所有(m+1)!(mn+1)種狀態(tài)和2m種決策（下一列的障礙情況），狀態(tài)轉(zhuǎn)移的時候需要做BFS，但是由于只需要用上一列的P值和新列，因此BFS時間2m+1當(dāng)i、P和決策一定時只需要BFS一次即可計算出新的P，因此對于所有b,計算d[i,P,b]的總時間為2m(2m+1+mn+1)=O(2mmn)分析(i,P)狀態(tài)有n*(m+1)!個，因此總時間為n(m+1)!*O(2mmn)=O(mn22mm!)。顯然和m有關(guān)的項比n大得多，因此總認為當(dāng)m大于n時交換m,n，并把矩陣翻轉(zhuǎn)?？梢杂脻L動數(shù)組，空間是O((m+1)!mn)的貪吃的九頭龍有N個果子的果樹，每個樹枝都有一個難受值把果子分成M份，每份給一個頭吃。每個頭至少吃一個果子，大頭必須吃果子1，且一共吃K