1、ACM程序設(shè)計(jì),東北林業(yè)大學(xué) 陳宇 Lg_,2020/9/25,2,今天你AC 了嗎？,2020/9/25,3,第7講,DP（二）,2020/9/25,4,我校的ACM在線評(píng)測(cè)系統(tǒng), 課件下載地址： ,2020/9/25,5,Function Run Funnefu16,We all love recursion! Dont we? Consider a three-parameter recursive function w(a, b, c): if a 20 or b 20 or c 20, then w(a, b, c) returns: w(20, 20, 20) if a b and

2、 b c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) This is an easy function to implement. The problem is, if implemented directly, for moderate values of a, b and c (for example, a = 15,

3、b = 15, c = 15), the program takes hours to run because of the massive recursion.,2020/9/25,6,input The input for your program will be a series of integer triples, one per line, until the end-of-file flag of -1 -1 -1. Using the above technique, you are to calculate w(a, b, c) efficiently and print t

4、he result.,2020/9/25,7,output Print the value for w(a,b,c) for each triple.,2020/9/25,8,sample_input 1 1 1 2 2 2 10 4 6 50 50 50 -1 7 18 -1 -1 -1,2020/9/25,9,思路：遞歸好,long long data212121; long long inf(int x,int y,int z) if (x20|y20|z20) return inf(20,20,20); if (xy ,2020/9/25,10,else if (dataxyz=-1)

5、 dataxyz=inf(x-1,y,z)+inf(x-1,y-1,z)+inf(x-1,y,z-1)-inf(x-1,y-1,z-1); return dataxyz; ,2020/9/25,11,main()函數(shù),int main(int argc, char *argv) int x,y,z; while(cinxyz) if (x=-1 ,2020/9/25,12,Recaman Sequence nefu91,The Recamans sequence is defined by a0 = 0 ; for m 0, am = am1 m if the rsulting am is p

6、ositive and not already in the sequence, otherwise am = am1 + m. The first few numbers in the Recamans Sequence is 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9 . Given k, your task is to calculate ak.,2020/9/25,13,input The input consists of several test cases. Each line of the input contains

7、 an integer k where 0 = k = 500000. The last line contains an integer 1, which should not be processed.,2020/9/25,14,output For each k given in the input, print one line containing ak to the output.,2020/9/25,15,sample_input 7 10000 -1,2020/9/25,16,分析：從下往上，打表也行,#define size 500000 int datasize+1; bo

8、ol inpsize*10;,2020/9/25,17,int main(int argc, char *argv),int n; memset(inp,false,sizeof(inp); data0=0;inp0=true; for(int i=1;i0 ,2020/9/25,18,while(cinn ,2020/9/25,19,滑雪 nefu18,description 每到冬天,信息學(xué)院的張健老師總愛到二龍山去滑雪,喜歡滑雪百這并不奇怪， 因?yàn)榛┑拇_很刺激?？墒菫榱双@得速度，滑的區(qū)域必須向下傾斜，而且當(dāng)你滑到坡底，你不得不再次走上坡或者等待升降機(jī)來載你。張老師想知道載一個(gè)區(qū)域中最長(zhǎng)

9、底滑坡。區(qū)域由一個(gè)二維數(shù)組給出。數(shù)組的每個(gè)數(shù)字代表點(diǎn)的高度。,2020/9/25,20,input 輸入的第一行表示區(qū)域的行數(shù)R和列數(shù)C(1 = R,C = 100)。下面是R行，每行有C個(gè)整數(shù)，代表高度h，0=h=10000。 output 輸出最長(zhǎng)區(qū)域的長(zhǎng)度。,2020/9/25,21,sample_input 5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一個(gè)人可以從某個(gè)點(diǎn)滑向上下左右相鄰四個(gè)點(diǎn)之一，當(dāng)且僅當(dāng)高度減小。在上面的例子中， 一條可滑行的滑坡為24-17-16-1。當(dāng)然25-24-23

10、-.-3-2-1更長(zhǎng)。 事實(shí)上，這是最長(zhǎng)的一條。,2020/9/25,22,sample_output 25,2020/9/25,23,分析：遞歸,int data101101; int inp101101; int m,n;,2020/9/25,24,int f(int i,int j) int max1,max2; int max_right=0,max_left=0,max_up=0,max_down=0; if (dataij0) return dataij; if (j+1inpij+1) max_right=f(i,j+1);/右邊 if (j-1=1 ,2020/9/25,25,

11、int main(int argc, char *argv),memset(data,0,sizeof(data); int k,max_all; while(cinmn) max_all=0; for(int i=1;iinpij; for(int i=1;i=m;i+) for(int j=1;j=n;j+) k=f(i,j);,2020/9/25,26,for(int i=1;i=m;i+) for(int j=1;j=n;j+) if (max_alldataij) max_all=dataij; coutmax_allendl; system(PAUSE); return EXIT_

12、SUCCESS; ,2020/9/25,27,采藥 nefu19,description 辰辰是個(gè)很有潛能、天資聰穎的孩子，他的夢(mèng)想是稱為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到個(gè)到處都是草藥的山洞里對(duì)他說：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大?！?如果你是辰辰，你能完成這個(gè)任務(wù)嗎？,2020/9/25,28,input 輸入的第一行有兩個(gè)整數(shù)T（1 = T = 1000

13、）和M（1 = M = 100），T代表總共能夠用來采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個(gè)在1到100之間（包括1和100）的的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。,2020/9/25,29,output 輸出只包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。,2020/9/25,30,sample_input 70 3 71 100 69 1 1 2,2020/9/25,31,代碼分析：可遞歸，也可遞推,int time_11001,value101; int data1001101; int t,n;,2020/9/25,32,int dp(int t1,int i) if (datat1i0) return datat1i; if (t1=0|in) return 0; if (t1=time_1i) datat1i=max(dp(t1-time_1i,i+1)+valuei,d