1、ACM程序設(shè)計(jì)福州大學(xué)至誠學(xué)院 馮新2022/10/121ACM程序設(shè)計(jì)福州大學(xué)至誠學(xué)院 馮新2022/10/91第九講動(dòng)態(tài)規(guī)劃初步2022/10/122第九講動(dòng)態(tài)規(guī)劃初步2022/10/92一、經(jīng)典問題：數(shù)塔問題 有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。2022/10/123一、經(jīng)典問題：數(shù)塔問題 有形如下圖所示的Input輸入數(shù)據(jù)首先包括一個(gè)整數(shù)C,表示測(cè)試實(shí)例的個(gè)數(shù)，每個(gè)測(cè)試實(shí)例的第一行是一個(gè)整數(shù)N(1 = N 109=10億）。試想一下：2022/10/126這道題如果用枚舉法（暴力思想），在數(shù)塔層數(shù)稍大的

2、情況下（如 拒絕暴力，倡導(dǎo)和諧2022/10/127 拒絕暴力，倡導(dǎo)和諧2022/10/97從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。同樣，下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時(shí)就非常明了。如數(shù)字2，只要選擇它下面較大值的結(jié)點(diǎn)19前進(jìn)就可以了。所以實(shí)際求解時(shí)，可從底層開始，層層遞進(jìn)，最后得到最大值。結(jié)論：自頂向下的分析，自底向上的計(jì)算?？紤]一下：2022/10/128從頂點(diǎn)出發(fā)時(shí)到底向左走還是向右走應(yīng)取決于是從左走能取到最有公式：MaxSumrj

3、= arj r=N=Max(MaxSumr+1j,MaxSumr+1j+1)+arj r=其他2022/10/129有公式：2022/10/99int main() int a100100; int sum100100; int t,i,j; scanf(%d,&t); while(t-) int n; scanf(%d,&n); for(i=0;in;i+) for(j=0;j=0;i-) for(j=0;j=i;j+) sumij=aij; if(i!=n-1)sumij=max(sumi+1j,sumi+1j+1)+sumij; printf(%dn,sum00); return 0;#

4、include int max(int a,int b) if(ab)return a; else return b;2022/10/1210int main()#include 20許多求最優(yōu)解的問題可以用動(dòng)態(tài)規(guī)劃來解決。用動(dòng)態(tài)規(guī)劃解題首先要把原問題分解成若干個(gè)子問題，子問題的解一旦求出就被保存。找到子問題，就意味著找到了將整個(gè)問題逐漸分解的辦法，因?yàn)樽訂栴}可以用相同的思路分解成子問題，一直分解下去，直到最底層規(guī)模最小的問題一目了然看出解。每層問題的解決，會(huì)導(dǎo)致上層問題的解決，逐層向上，就會(huì)導(dǎo)致整個(gè)問題的解決，我們可采取自底層的子問題開始，自底向上的推導(dǎo)出一個(gè)個(gè)子問題的解。2022/10/1

5、211許多求最優(yōu)解的問題可以用動(dòng)態(tài)規(guī)劃來解決。用動(dòng)態(tài)規(guī)劃解題首先要二、經(jīng)典問題：最長有序子序列2022/10/1212二、經(jīng)典問題：最長有序子序列2022/10/912二、經(jīng)典問題：最長有序子序列問題描述一個(gè)數(shù)的序列bi，當(dāng)b1 b2 . bS的時(shí)候，我們稱這個(gè)序列是上升的。對(duì)于給定的一個(gè)序列(a1, a2, ., aN)，我們可以得到一些上升的子序列(ai1, ai2, ., aiK)，這里1 = i1 i2 . iK = N。比如，對(duì)于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中最長的長度是4，比如子序列(1,

6、 3, 5, 8). 你的任務(wù)，就是對(duì)于給定的序列，求出最長上升子序列的長度。2022/10/1213二、經(jīng)典問題：最長有序子序列問題描述2022/10/913二、經(jīng)典問題：最長有序子序列輸入數(shù)據(jù)輸入的第一行是序列的長度N (1 = N = 1000)。第二行給出序列中的N個(gè)整數(shù)，這些整數(shù)的取值范圍都在0到10000。輸出要求最長上升子序列的長度。輸入樣例71 7 3 5 9 4 8輸出樣例42022/10/1214二、經(jīng)典問題：最長有序子序列輸入數(shù)據(jù)2022/10/914二、經(jīng)典問題：最長有序子序列如何把這個(gè)問題分解成子問題呢？經(jīng)過分析，發(fā)現(xiàn) “求以ak（k=1, 2, 3N）為終點(diǎn)的最長上

7、升子序列的長度”是個(gè)好的子問題這里把一個(gè)上升子序列中最右邊的那個(gè)數(shù)，稱為該子序列的“終點(diǎn)”。雖然這個(gè)子問題和原問題形式上并不完全一樣，但是只要這N個(gè)子問題都解決了，那么這N個(gè)子問題的解中，最大的那個(gè)就是整個(gè)問題的解。MaxLen (1) = 1MaxLen (k) = Max MaxLen (i)：1i k 且 ai ak且 k1 + 1MaxLen(k)的值，就是在ak左邊，“終點(diǎn)”數(shù)值小于ak，且長度最大的那個(gè)上升子序列的長度再加1。因?yàn)閍k左邊任何“終點(diǎn)”小于ak的子序列，加上ak后就能形成一個(gè)更長的上升子序列。 2022/10/1215二、經(jīng)典問題：最長有序子序列如何把這個(gè)問題分解成子

8、問題呢？經(jīng)解決方案：2022/10/1216解決方案：2022/10/916#include #define MAX_N 1000int bMAX_N + 10;int aMaxLenMAX_N + 10;int main() int N,i,j,nMax, nTmp; scanf(%d, & N); for( i = 1;i = N;i + ) scanf(%d, & bi); aMaxLen1 = 1; for( i = 2; i = N; i + ) /*每次求以第i個(gè)數(shù)為終點(diǎn)的最長上升子序列的長度*/ nTmp = 0; /*記錄滿足條件的，第i個(gè)數(shù)左邊的上升子序列的最大長度*/ for( j = 1; j bj ) if( nTmp aMaxLenj ) nTmp = aMaxLenj; aMaxLeni = nTmp + 1; nMax = -1; for( i =