第二次課動態(tài)規(guī)劃第1頁，課件共84頁，創(chuàng)作于2023年2月本周POJ上做題：動態(tài)規(guī)劃1037Adecorativefence、1050TotheMax、

1088滑雪、 1125StockbrokerGrapevine、

1141BracketsSequence、 1159Palindrome、

1160PostOffice、 1163TheTriangle、

1458CommonSubsequence、 1579FunctionRunFun、

1887TestingtheCATCHER、 1953WorldCupNoise、

2386LakeCounting第2頁，課件共84頁，創(chuàng)作于2023年2月

動態(tài)規(guī)劃是1951年由美國數(shù)學家貝爾曼（RichardBellman)提出，它是解決一類多階段決策問題的優(yōu)化方法，也是考察問題的一種途徑。動態(tài)規(guī)劃方法是現(xiàn)代企業(yè)管理中的一種重要決策方法。如果一個問題可將其過程劃分為若干個相互聯(lián)系的階段問題，且它的每一階段都需進行決策，則這類問題均可用動態(tài)規(guī)劃方法進行求解。根據(jù)多階段決策過程的時序和決策過程的演變，動態(tài)規(guī)劃方法有以下四種類型：離散確定型、離散隨機型、連續(xù)確定型和連續(xù)隨機型。第3頁，課件共84頁，創(chuàng)作于2023年2月幾類算法的經(jīng)典名言動態(tài)規(guī)劃：不做重復的事；貪心法：只選最好的；分支定界法：沒戲的就殺掉；回溯法：碰壁就回頭。作人生規(guī)劃要善于利用動態(tài)規(guī)劃；找女朋友要善于利用好貪心算法；人生重大決策要活學活用回溯法；第4頁，課件共84頁，創(chuàng)作于2023年2月算法總體思想動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=第5頁，課件共84頁，創(chuàng)作于2023年2月為什么動態(tài)規(guī)劃比遞歸算法有效？但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次，因此利用遞歸算法得到的算法往往是指數(shù)復雜度的算法。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)第6頁，課件共84頁，創(chuàng)作于2023年2月POJ2753Fibonacci數(shù)列例子：確定Fibonaccisequencefn項的值:考慮Fibonaccisequence的遞歸定義:我們將得到如下的遞歸算法:在POJ上遞交之后，返回的結果是：TimeLimited。而不是可愛的ACWhy？第7頁，課件共84頁，創(chuàng)作于2023年2月子問題的重疊性將上述遞歸算法展開:可以看出f(n-1)被調用1次,f(n-2)被調用2次,等等.這將導致大量的調用最終解為：第8頁，課件共84頁，創(chuàng)作于2023年2月樹形遞歸計算過程中存在冗余計算，為了除去冗余計算，可以從已知條件開始計算，并記錄計算過程中的中間結果。f(5)f(3)f(2)f(1)f(2)f(4)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)f(1)11001010冗余計算第9頁，課件共84頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃例：POJ2753Fibonacci數(shù)列intf[n+1];f[1]=f[2]=1;intI;for(i=3;i<=n;i++)f[i]=f[i-1]+f[i-2];cout<<f[n]<<endl;用空間換時間第10頁，課件共84頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃算法的基本要素一、最優(yōu)子結構一個最優(yōu)化策略具有這樣的性質，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其為最優(yōu)子結構性質。同一個問題可以有多種方式刻劃它的最優(yōu)子結構，有些表示方法的求解速度更快（空間占用小，問題的維度低）例如：最短路徑問題。abc在分析問題的最優(yōu)子結構性質時，所用的方法具有普遍性：首先假設由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后再設法說明在這個假設下可構造出比原問題最優(yōu)解更好的解，從而導致矛盾。第11頁，課件共84頁，創(chuàng)作于2023年2月動態(tài)規(guī)劃算法的基本要素二、重疊子問題遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結果。通常不同的子問題個數(shù)隨問題的大小呈多項式增長。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。第12頁，課件共84頁，創(chuàng)作于2023年2月一、例子（最短路問題）假如上圖是一個線路網(wǎng)絡，兩點之間連線上的數(shù)字表示兩點間的距離（或費用），我們的問題是要將貨物從A地運往E地，中間通過B、C、D三個區(qū)域，在區(qū)域內(nèi)有多條路徑可走，現(xiàn)求一條由A到E的線路，使總距離最短（或總費用最小）。AB1B2B3C1C2C3D1D2E24374632426534633334第13頁，課件共84頁，創(chuàng)作于2023年2月將該問題劃分為4個階段的決策問題第一階段為從A到Bj（j=1，2，3），有三種決策方案可供選擇；第二階段為從Bj到Cj（j=1,2,3），也有三種方案可供選擇；第三階段為從Cj到Dj(j=1,2)，有兩種方案可供選擇；第四階段為從Dj到E，只有一種方案選擇。AB1B2B3C1C2C3D1D2E24374632426534633334第14頁，課件共84頁，創(chuàng)作于2023年2月如果用完全枚舉法，則可供選擇的路線有3×3×2×1=18（條），將其一一比較才可找出最短路線：A→B1→C2→D3→E其長度為12。

AB1B2B3C1C2C3D1D2E24374632426534633334第15頁，課件共84頁，創(chuàng)作于2023年2月顯然，這種方法是不經(jīng)濟的，特別是當階段數(shù)很多，各階段可供的選擇也很多時，這種解法甚至在計算機上完成也是不現(xiàn)實的。由于我們考慮的是從全局上解決求A到E的最短路問題，而不是就某一階段解決最短路線，因此可考慮從最后一階段開始計算，由后向前逐步推至A點：第16頁，課件共84頁，創(chuàng)作于2023年2月第四階段，由D1到E只有一條路線，其長度f4（D1）=3，同理f4（D2）=4。第三階段，由Cj到Di分別均有兩種選擇，即，決策點為D1AB1B2B3C1C2C3D1D2E24374632426534633334第17頁，課件共84頁，創(chuàng)作于2023年2月,決策點為D1，決策點為D2AB1B2B3C1C2C3D1D2E24374632426534633334第18頁，課件共84頁，創(chuàng)作于2023年2月第二階段，由Bj到Cj分別均有三種選擇，即：決策點為C2

AB1B2B3C1C2C3D1D2E24374632426534633334第19頁，課件共84頁，創(chuàng)作于2023年2月決策點為C1或C2決策點為C2

AB1B2B3C1C2C3D1D2E24374632426534633334第20頁，課件共84頁，創(chuàng)作于2023年2月第一階段，由A到B，有三種選擇，即：決策點為B3f1（A）=15說明從A到E的最短距離為12，最短路線的確定可按計算順序反推而得。即A→B3→C2→D2→E上述最短路線問題的計算過程，也可借助于圖形直觀的表示出來：AB1B2B3C1C2C3D1D2E24374632426534633334第21頁，課件共84頁，創(chuàng)作于2023年2月圖中各點上方框的數(shù)，表示該點到E的最短距離。圖中紅箭線表示從A到E的最短路線。從引例的求解過程可以得到以下啟示：①對一個問題是否用上述方法求解，其關鍵在于能否將問題轉化為相互聯(lián)系的決策過程相同的多個階段決策問題。

AB1B2B3C1C2C3D1D2E2437463242653463333434676991112第22頁，課件共84頁，創(chuàng)作于2023年2月所謂多階段決策問題是：把一個問題看作是一個前后關聯(lián)具有鏈狀結構的多階段過程，也稱為序貫決策過程。如下圖所示：②在處理各階段決策的選取上，不僅只依賴于當前面臨的狀態(tài)，而且還要注意對以后的發(fā)展。即是從全局考慮解決局部（階段）的問題。③各階段選取的決策，一般與“時序”有關，決策依賴于當前的狀態(tài)，又隨即引起狀態(tài)的轉移，整個決策序列就是在變化的狀態(tài)中產(chǎn)生出來，故有“動態(tài)”含義。因此，把這種方法稱為動態(tài)規(guī)劃方法。④決策過程是與階段發(fā)展過程逆向而行。第23頁，課件共84頁，創(chuàng)作于2023年2月攔截導彈（poj1887）某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。第24頁，課件共84頁，創(chuàng)作于2023年2月輸入 輸入數(shù)據(jù)為導彈依次飛來的高度，所有高度值均為不大于30000的正整數(shù)。輸出 輸出只有一行是這套系統(tǒng)最多能攔截的導彈數(shù)。第25頁，課件共84頁，創(chuàng)作于2023年2月輸入樣例 38920715530029917015865輸入樣例 6第26頁，課件共84頁，創(chuàng)作于2023年2月題目分析因為只有一套導彈攔截系統(tǒng)，并且這套系統(tǒng)除了第一發(fā)炮彈能到達任意高度外，以后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度；所以，被攔截的導彈應該按飛來的高度組成一個非遞增序列。題目要求我們計算這套系統(tǒng)最多能攔截的導彈數(shù)，并依次輸出被攔截導彈的高度，實際上就是要求我們在導彈依次飛來的高度序列中尋找一個最長非遞增子序列。第27頁，課件共84頁，創(chuàng)作于2023年2月設X={x1,x2,…,xn}為依次飛來的導彈序列，Y={y1,y2,…,yk}為問題的最優(yōu)解（即X的最長非遞增子序列），s為問題的狀態(tài)（表示導彈攔截系統(tǒng)當前發(fā)送炮彈能夠到達的最大高度，初值為s=∞——第一發(fā)炮彈能夠到達任意的高度）。第28頁，課件共84頁，創(chuàng)作于2023年2月如果y1=x1，即飛來的第一枚導彈被成功攔截。那么，根據(jù)題意“每一發(fā)炮彈都不能高于前一發(fā)的高度”，問題的狀態(tài)將由s=∞變成s≤x1（x1為第一枚導彈的高度）；第29頁，課件共84頁，創(chuàng)作于2023年2月在當前狀態(tài)下，序列Y1={y2,…,yk}也應該是序列X1={x2,…,xn}的最長非遞增子序列（大家用反證法很容易證明）。也就是說，在當前狀態(tài)s≤x1下，問題的最優(yōu)解Y所包含的子問題（序列X1）的解（序列Y1）也是最優(yōu)的。這就是攔截導彈問題的最優(yōu)子結構性質。第30頁，課件共84頁，創(chuàng)作于2023年2月設D(i)為第i枚導彈被攔截之后，這套系統(tǒng)最多還能攔截的導彈數(shù)（包含被攔截的第i枚）。我們可以設想，當系統(tǒng)攔截了第k枚導彈xk，而xk又是序列X={x1,x2,…,xn}中的最小值，即第k枚導彈為所有飛來的導彈中高度最低的，則有D(k)=1；當系統(tǒng)攔截了最后一枚導彈xn，那么，系統(tǒng)最多也只能攔截這一枚導彈了，即D(n)=1；其它情況下，也應該有D(i)≥1。第31頁，課件共84頁，創(chuàng)作于2023年2月根據(jù)以上分析，可歸納出問題的動態(tài)規(guī)劃遞歸方程為：第32頁，課件共84頁，創(chuàng)作于2023年2月假設系統(tǒng)最多能攔截的導彈數(shù)為dmax（即問題的最優(yōu)值），則dmax（i為被系統(tǒng)攔截的第一枚導彈的順序號）第33頁，課件共84頁，創(chuàng)作于2023年2月所以，要計算問題的最優(yōu)值dmax，需要分別計算出D（1）、D（2）、……D（n）的值，然后將它們進行比較，找出其中的最大值。第34頁，課件共84頁，創(chuàng)作于2023年2月根據(jù)上面分析出來的遞歸方程，我們完全可以設計一個遞歸函數(shù)，采用自頂向下的方法計算D（i）的值。然后，對i從1到n分別調用這個遞歸函數(shù)，就可以計算出D（1）、D（2）、……D（n）。第35頁，課件共84頁，創(chuàng)作于2023年2月但這樣將會有大量的子問題被重復計算。比如在調用遞歸函數(shù)計算D（1）的時候，可能需要先計算D（5）的值；之后在分別調用遞歸函數(shù)計算D（2）、D（3）、D（4）的時候，都有可能需要先計算D（5）的值。如此一來，在整個問題的求解過程中，D（5）可能會被重復計算很多次，從而造成了冗余，降低了程序的效率。第36頁，課件共84頁，創(chuàng)作于2023年2月其實，通過以上分析，我們已經(jīng)知道：D（n）=1。如果將n作為階段對問題進行劃分，根據(jù)問題的動態(tài)規(guī)劃遞歸方程，我們可以采用自底向上的方法依次計算出D（n-1）、D（n-2）、……D（1）的值。這樣，每個D（i）的值只計算一次，并在計算的同時把計算結果保存下來，從而避免了有些子問題被重復計算的情況發(fā)生，提高了程序的效率。第37頁，課件共84頁，創(chuàng)作于2023年2月intmain（）{inth[2000],d[2000],count,c,max,i,j;//h表示高度值，d表示最優(yōu)值，c是能攔截得最多導彈數(shù)count=0;while（scanf（"%d",h+count++）!=EOF）; //輸入高度d[count-1]=1;c=1;for（i=count-2;i<0;i--）{ //用動態(tài)規(guī)劃計算所有最優(yōu)值max=0; for（j=i+1;j>count;j++） if（(h[i]>=h[j])&&max<d[j]）max=d[j];d[i]=max+1;if(c<d[i])c=d[i];}printf（"%d\n",c）;}第38頁，課件共84頁，創(chuàng)作于2023年2月思考題上述問題修改成：要求攔截所有導彈，則需要多少套上述系統(tǒng)？第39頁，課件共84頁，創(chuàng)作于2023年2月實例POJ2122：FlightPlanning

Yourjobistowriteaprogramthatplansairplaneflights.Eachflightconsistsofaseriesofoneormorelegs.Yourprogrammustchoosethebestaltitudeforeachlegtominimizetheamountoffuelconsumptionduringthetrip.

第40頁，課件共84頁，創(chuàng)作于2023年2月 Theairplanehasafixedairspeed,givenbytheconstantVCRUISE,andamost-efficientcruisingaltitude,AOPT.WhenflyingataltitudeAOPT,fuelconsumptioningallonsperhourisgivenbyGPHOPT.WhenflyingatanaltitudethatisdifferentfromAOPT,fuelconsumptionincreasesbyGPHEXTRAforeach1000feetaboveorbelowAOPT.第41頁，課件共84頁，創(chuàng)作于2023年2月 Theflightstartsandfinishesatanaltitudeof0.Each1000footclimbburnsanextraamountoffuelgivenbyCLIMBCOST(thereisnoreductioninfuelconsumptionwhenyoudescend).Maketheapproximationthatallclimbinganddescendingisdoneinzerotimeatthebeginningofeachflightleg.第42頁，課件共84頁，創(chuàng)作于2023年2月 Thuseachlegisflownataconstantairspeedandaltitude.Forthisproblem,theairplanecharacteristicsaregivenbythefollowingconstants:第43頁，課件共84頁，創(chuàng)作于2023年2月

VCRUISE400knots(aknotisonenauticalmile(1.852km)perhour)

AOPT30,000feet GPHOPT2000gallonsperhour GPHEXTRA10gallonsperhourforeach1000feet CLIMBCOST50gallonsper1000feetofclimb第44頁，課件共84頁，創(chuàng)作于2023年2月 Beforeeachflight,youaregiventhelengthofeachlegandthetailwindexpectedforeachleg.Apositivetailwindincreasestheairplane’sspeedovertheground,andanegativetailwinddecreasesitsspeedovertheground. Forexample,ifairspeedis400knotsandthetailwindis-50knots,speedoverthegroundis350knots.第45頁，課件共84頁，創(chuàng)作于2023年2月Bypolicy,altitudeforeachlegmustbesomeintegermultipleof1000feet,between20,000and40,000feet,inclusive.Yourprogrammustcomputethebestaltitudeforeachlegtominimizeoverallfuelconsumptionforthetrip,andmustcomputethefuelrequiredforthetrip.第46頁，課件共84頁，創(chuàng)作于2023年2月Input ThefirstlinecontainsanintegerN,representingthenumberofflightsyouarerequiredtoplan.Eachflightconsistsofthefollowinginputlines: ThefirstinputlineinaflightcontainsanintegerK(0<K<10),representingthenumberoflegsintheflight.ThenextKinputlineseachcontainthefollowingthreeintegers: (1)Thelengthoftheleg,innauticalmiles (2)Theexpectedtailwindat20,000feet,inknots (3)Theexpectedtailwindat40,000feet,inknots第47頁，課件共84頁，創(chuàng)作于2023年2月Theexpectedtailwindataltitudesbetween20,000and40,000feetiscomputedbylinearinterpolation.Forexample,theexpectedtailwindat30,000feetishalfwaybetweentheexpectedtailwindat20,000feetandtheexpectedtailwindat40,000feet.第48頁，課件共84頁，創(chuàng)作于2023年2月Output Yourprogrammustproduceoneoutputlineforeachflight.Theoutputlinemustcontaintheflightnumber(countingfromthebeginningoftheproblem),thechosenaltitudeforeachleg(inthousandsoffeet),andthefuelrequiredforthetrip(ingallons,tothenearestgallon).第49頁，課件共84頁，創(chuàng)作于2023年2月SampleInput221500-50501000003100050020000201800-50100OutputfortheSampleInputFlight1:353013985Flight2:20304023983第50頁，課件共84頁，創(chuàng)作于2023年2月圖例：第51頁，課件共84頁，創(chuàng)作于2023年2月轉換為多段圖問題FlightPlan可以轉換為多段圖問題，每一條邊代表某段由前一段飛行高度飛到本段的某一飛行高度的燃油消耗量第52頁，課件共84頁，創(chuàng)作于2023年2月Analysis一、計算飛機在地域i的耗油量假設飛機在地域i-1（2≤i≤k+1）的海拔高度為l，飛到地域i的海拔高度為m，計算飛機在地域i的耗油量g[i,l,m]必須考慮如下幾個因素：（注意：為了方便計算，飛行高度和風速以1000feet為單位）1.上升過程增加的耗油量a由于飛機每上升一個單位，需要增加climbcost的耗油量，因此

第53頁，課件共84頁，創(chuàng)作于2023年2月Analysis2.每小時的實際耗油量b飛機在海拔高度aopt飛行時每小時耗油gphopt.當飛機在m高度飛行時，與aopt的垂直距離為個單位。每垂直偏離aopt高度一個單位，需要增加耗油量gphextra.因此第54頁，課件共84頁，創(chuàng)作于2023年2月3.在地域i的實際飛行時間cc=地域i的長度/地域i的實際飛行速度由于地域i的風速垂直反向線性變化，m單位處的風速為在20單位處的風速與40單位處的風速的平均數(shù)，因此地域i的等高風速為

第55頁，課件共84頁，創(chuàng)作于2023年2月而飛機的實際速度為VCRUISE與地域i等高風速的矢量和，因此c=地域i的長度/(地域i的等高風速＋VCRUISE)顯而易見，第56頁，課件共84頁，創(chuàng)作于2023年2月二．規(guī)劃飛行方案

設為在確定地域i的飛行高度為j的情況下，飛機由地域l飛至地域i所耗費的最小總耗油量；為記憶表。飛機由地域i-l的高度到達地域i的j高度，可使總耗油量最小，即

第57頁，課件共84頁，創(chuàng)作于2023年2月問題是怎么才能計算呢？首先我們必須明確，按最優(yōu)性要求確定了飛機在地域i-1的飛行為高度為; 由于為一個定值，因此的值必須最小。不然的話，將它替換到表達式中，則可使表達式值變得更小，出現(xiàn)矛盾，這就說明問題的最優(yōu)解包含了子問題的最優(yōu)解，即該問題具備了最優(yōu)子結構。第58頁，課件共84頁，創(chuàng)作于2023年2月

下面我們來分析一下最優(yōu)表達式的構造：飛機由地域1起飛，因此data[1,j]=g[1,0,j](20≤j≤40).然后順序計算， data[2,20]…data[2,40],data[3,20],…,data[3,40],.....data[k,20],…,data[k,40].第59頁，課件共84頁，創(chuàng)作于2023年2月

在計算data[i,j]時，我們無法預計飛機在地域i-1應以怎樣的高度飛行方可使表達式的值最小。因此只能一一假設飛機在地域i-1的高度為20,21,…,40,即分別求出從上述21個表達式中選出值最小的一個，即：將滿足上式的飛行高度L存入記憶表data2[i,j]第60頁，課件共84頁，創(chuàng)作于2023年2月

由此可見，在求data[i,j]的過程中不斷查閱子問題的解data[i-1,20]...data[i-1,40]。顯然這個最優(yōu)化問題包含了重疊子問題，采用動態(tài)程序設計方法是最合適不過的了，按照上述分析，我們可以直接寫出動態(tài)規(guī)劃的方程：1≤i≤k20≤j≤4020≤l≤40第61頁，課件共84頁，創(chuàng)作于2023年2月

求解data表和data2表的算法十分簡單：forj:=20to40dodata[1,j]←g[1,0,j];/*構造記憶表*/fori:=2tokdoforj:=20to40dofori:=20to40dobegin計算data[i,j]=min{data[i-1,l],g[i,l,j]};將滿足上式的l記入記憶表data2[i,j];end:{for}第62頁，課件共84頁，創(chuàng)作于2023年2月三.輸出飛行計劃有了記憶表data2我們便可以從地域k出發(fā)倒推飛機在各地域的飛行高度data3:

forj:=20to40dodata3[k]←計算滿足min{data[k,j]}的j;fori:=kdownto2dodata3[i-l]←data2{i,data3[i]};最后輸出飛行計劃：fori=1tokdo輸出飛機在地域i的飛行高度data3[i];輸出最小的總耗油量data[k,data3[k]];

每輸入一條航線信息，我們便使用上述方法規(guī)劃該航線的飛行方案，直至n條航線規(guī)劃完畢第63頁，課件共84頁，創(chuàng)作于2023年2月Uxuhul的表決Uxuhul印第安人是世界上最古老的文明之一。在中美洲叢林中，大約從公元前3200年的黃金時代，Uxuhul文化繁榮了近千年。每年代表各階層的高級牧師都會聚集在首都，投票表決重要事情。每次嚴格限定表決三個議案，每個議案只有是/否的回答。三個議案在議論表決中同時決定，遵循下列形式：第64頁，課件共84頁，創(chuàng)作于2023年2月所有牧師聚集在一大房間，房間中央有一張桌子。在桌子上放了三片石塊，一面黑，一面白。每個石塊代表一個議案，黑表示“否”，白表示“是”。最初所有的石塊都是黑色的面朝上，表示所有的議案都是否定的結果。根據(jù)年齡，從年輕的到年長者，每位牧師通過翻動一塊石塊來表決，也就是改變某個議案的結果。不允許不表決。最年長的牧師做出選擇后，石塊朝上的顏色決定了三個議案的最終結果。第65頁，課件共84頁，創(chuàng)作于2023年2月Uxuhul的政治相當復雜，大量代表不同利益的游說（和行賄），影響三個議案的八種結果。宗教規(guī)則強制每位牧師在投票表決前公開他們對三個議案的八種結果的表決傾向。由于彼此間都知道表決傾向，每位牧師都爭取對自己最有利的結果，而且Uxuhul人具有高超的邏輯推理能力，對游戲規(guī)則又很了解，每個牧師都能找到最理想的方法！第66頁，課件共84頁，創(chuàng)作于2023年2月最后，復雜刻板行政系統(tǒng)導致Uxuhul文明的崩潰。只留下他們的城市和廟宇，歷史學家和考古學家試圖通過研究每年議案的表決結果來弄清他們的歷史。不管怎么說，只有牧師們的表決傾向留下來了，沒有實際的表決結果。那么你的任務就是揭示出表決結果。第67頁，課件共84頁，創(chuàng)作于2023年2月輸入輸入從一個整數(shù)n開始,1<=n<=100，代表表決的次數(shù)。后面跟著n個問題。每次表決由一個整數(shù)m開始，1<=m<=100，表示牧師的數(shù)目。后面m行，按照順序代表每位投票者的表決傾向。對于每種結果（NNN,NNY,NYN,NYY,YNN,YNY,YYN,YYY,‘N’表示否，‘Y’表示是）,給一個[1…8]之間的數(shù)，越小的數(shù)字表示選擇可能性越大。對8種結果的表決傾向按照前面列舉的順序的給出。第68頁，課件共84頁，創(chuàng)作于2023年2月輸出對于每個問題，輸出三個議案的表決結果。‘N’表示否，‘Y’表示是。第69頁，課件共84頁，創(chuàng)作于2023年2月輸入樣例2487654321863124578365127412345678112345678第70頁，課件共84頁，創(chuàng)作于2023年2月輸出樣例NYYNNY第71頁，課件共84頁，創(chuàng)作于2023年2月解題思路這個題似乎可以采用貪心來做。每一個牧師都從可能的結果中選擇對自己最有利的結果，最后的結果似乎就是人人都滿意的結果？仔細分析就發(fā)現(xiàn)這種思路不正確。假如有兩個人來選擇，選擇傾向是：2174583638645127第72頁，課件共84頁，創(chuàng)作于2023年2月如果按照貪心的思想去做，第一個人應該選擇NNY,但第二個人肯定會選擇成YNY，結果是第一個人最不滿意的。如果第一個人選擇NYN，表面上是他不滿意的選擇（排在第七位的結果），但第二個人會選擇YYN（這是他在這種情況下的最好選擇，排在第二位）,而對于第一個人來說，YYN也是一個不錯的結果。第73頁，課件共84頁，創(chuàng)作于2023年2月所以，貪心的思路不行。在解決這個題之前，讓我們先看看海盜的傳說：第74頁，課件共84頁，創(chuàng)作于2023年2月有5個海盜，多年的海上生活使他們積攢了100顆寶石。他們決定將寶石分掉之后就分手，洗手不干了。他們商量許久，最后決定：首先抽簽，每個人抽得一個號碼（1號到5號），然后1號海盜提出一個分配方案，所有海盜舉手表決，如果過半數(shù)的海盜同意該分配方案，則按此方案分配，否則將1號海盜扔到大海。再由2號海盜提出他的分配方案，重復以上過程，直到找到分配方案止。海盜都是很聰明的，而且彼此知道別人的聰明，每個海盜都希望得到最多的寶石。如果你是1號海盜，你會提出怎樣的分配方案，使你獲得最多的寶石且保住性命？第75頁，課件共84頁，創(chuàng)作于2023年2月因為海盜很聰明，所以你能想到的別的也能想到。我們從簡單情況出發(fā)：首先看4號海盜分配方案，只可能是0100（少1顆5號可不會投票支持）所以3號海盜分配方案，9910（首先5號一顆都不用給，因為只有100顆才能合他的胃口，4號一顆足矣，總比沒有強）第76頁，課件共84頁，創(chuàng)作于2023年2月2號海盜分配方案，97021（首先3號一顆都不用給，因為只有100顆才能合他的胃口，4號兩顆，5號一顆，要比3號分得多）所以1號海盜最佳分配方案，970102（原因同上，1，3，5號海盜投票支持）第77頁，課件共84頁，創(chuàng)作于2023年2月和海盜問題一樣，要倒過來思考，我們以楊例中的第一組數(shù)據(jù)來說明牧師是怎么思考的487654321863124578365127412345678第78頁，課件共84頁，創(chuàng)作于2023年2月首先最后投票的很簡單，從可能出現(xiàn)的結果里找個最喜歡的。倒數(shù)第二怎么投？假設他面對的是NYY，他可以變?yōu)閧NNY，NYN，YYY}，這其中他最喜歡的是NNY，但他就會選擇NNY嗎？不會！因為選擇NNY，最后（通過最后牧師表決）的結果就是NNN，是他最不喜歡的，他的選擇是YYY，因為最后的結果將是NYY，是可以得到的最好結果。從后往前，記錄當前祭司面對每種情況（NNN,NNY,NYN,NYY,YNN,YNY,YYN,YYY）下選擇能得到的最好結果。倒數(shù)第二個：836