樹規(guī)7題樹型動態(tài)七道題

1、樹型動態(tài)規(guī)劃七道題一、選課學(xué)校實行學(xué)分制。每門的必修課都有固定的學(xué)分，同時還必須獲得相應(yīng)的選修課程學(xué)分。學(xué)校開設(shè)了 N（N300）門的選修課程，每個學(xué)生可選課程的數(shù)量 M 是給定的。學(xué)生選修了這 M 門課并考核通過就能獲得相應(yīng)的學(xué)分。在選修課程中，有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如Frontpage必須在選修了Windows 操作基礎(chǔ)之后才能選修。稱Windows 操作基礎(chǔ)是Frontpage的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。每門課都有一個課號，依次為 1，2，3，。例如:表中過。是的先修課，2

2、 是 3、4 的先修課。如果要選 3，那么 1 和 2 都一定已被選修你的任務(wù)是為自己確定一個選課方案，使得你能得到的學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時間上的程序名：score輸入格式：。輸入文件的第一行包括兩個整數(shù) N、M（中間用一個空格隔開），其中 1N300,1MN。以下 N 行每行代表一門課。課號依次為 1，2，N。每行有兩個數(shù)（用一個空格隔開），第一個數(shù)為這門課先修課的課號（若不存在先修課則該項為 0），第二個數(shù)為這門課的學(xué)分。學(xué)分是不超過 10 的正整數(shù)。輸出格式：輸出文件只有一個數(shù)：實際所選課程的學(xué)分總數(shù)。輸入樣例：7 42 20 10 42 17 17

3、 62 2輸出樣例：13來源：CTSC二、Bob 喜歡玩電腦，特別是。但是他經(jīng)常無法找到快速玩過的辦法?，F(xiàn)在他有個問題。他要建立一個古城堡，城堡中的路形成一棵樹。他要在這棵樹的結(jié)點上放置課號先修課號學(xué)分1無121無最少數(shù)目的士兵，使得這些士兵能了望到所有的路。注意，某個士兵在一個結(jié)點上時，與該結(jié)點相連的所有邊將都可以被了望到。請你編一程序，給定一樹，幫 Bob 計算出他需要放置最少的士兵。程序名：stragedi輸入格式：輸入文件中數(shù)據(jù)表示一棵樹，描述如下：第一行 N，表示樹中結(jié)點的數(shù)目。第二行至第 N+1 行，每行描述每個結(jié)點信息，依次為：該結(jié)點標(biāo)號 i，k(后面有 k 條邊與結(jié)點 I 相連

4、)，接下來 k 個數(shù)，分別是每條邊的另一個結(jié)點標(biāo)號 r1，r2，.，rk。對于一個 n(0n=1500)個結(jié)點的樹，結(jié)點標(biāo)號在 0 到 n-1 之間，在輸入文件中每條邊只出現(xiàn)一次。輸出格式：輸出文件僅包含一個數(shù)，為所求的最少的士兵數(shù)目。例如，對于如下圖所示的樹：為 1（只要一個士兵在結(jié)點 1 上）。輸入樣例 1：40 1 11 2 2 32 03 0輸出樣例 1：1輸入樣例 2：53 30輸出樣例 2：2來源：SGOI三、沒有上司的Ural 大學(xué)有 N 個職員，為 1N。他們有從屬關(guān)系，也就是說他們的關(guān)系就像一棵以校長為根的樹，父結(jié)點就是子結(jié)點的直接上司。每個職員有一個指數(shù)。現(xiàn)在有個慶宴會，要

5、求與會職員的程序名：party輸入格式：指數(shù)最大。但是，沒有職員愿和直接上司一起與會。第一行一個整數(shù) N。(1=N=6000)接下來 N 行，第 i+1 行表示 i 號職員的指數(shù) Ri。(-128=Ri=127)接下來 N-1 行，每行輸入一對整數(shù) L,K。表示 K 是 L 的直接上司。最后一行輸入 0,0。輸出格式：輸出最大的輸入樣例：71111111指數(shù)。50 0輸入樣例：5來源：URAL四、二叉蘋果樹有一棵蘋果樹，如果樹枝有分叉，一定是分 2 叉（就是說沒有只有 1 個兒子的結(jié)點）。這棵樹共有 N 個結(jié)點（葉子點或者樹枝分叉點），為 1-N,樹根一定是 1。用一根樹枝兩端連接的結(jié)點的來描

6、述一根樹枝的位置。下面是一顆有 4 個樹枝的樹：25 /34 / 1現(xiàn)在這顆樹枝條太多了，需要剪枝。但是一些樹枝上長有蘋果。給定需要保留的樹枝數(shù)量，求出最多能留住多少蘋果。程序名：apple輸入格式：第 1 行 2 個數(shù)，N 和 Q(1=Q= N,1N=100)。N 表示樹的結(jié)點數(shù)，Q 表示要保留的樹枝數(shù)量。接下來 N-1 行描述樹枝的信息。每行 3 個整數(shù)，前兩個是它連接的結(jié)點的每根樹枝上的蘋果不超過 30000 個。輸出格式：一個數(shù)，最多能留住的蘋果的數(shù)量。輸入樣例：5 2。第 3 個數(shù)是這根樹枝上蘋果的數(shù)量。3 5 20輸入樣例：21來源：URAL(廣州六中信息學(xué)奧賽小組譯)五、比賽轉(zhuǎn)播

7、一個電視網(wǎng)絡(luò)計劃轉(zhuǎn)播一場重要的足球比賽。網(wǎng)絡(luò)中的傳輸點和接收點（即用戶）可以表示一棵樹。這棵樹的根是一個傳輸點，它將轉(zhuǎn)播比賽。樹的葉節(jié)點是可能要接受這場比賽的用戶（他當(dāng)然可以選擇不看比賽，這樣就不要交款）。其他非根節(jié)點，非葉節(jié)點的中間節(jié)點為數(shù)據(jù)的中轉(zhuǎn)站。將一個信號從一個傳輸點傳到另一個傳輸點的花費是給定的。整個轉(zhuǎn)播的費用就是每一個傳輸費用的總和。 每一個用戶（葉節(jié)點）都準(zhǔn)備付一定的錢來看這場比賽。電視網(wǎng)絡(luò)公司要決定是否要給這個用戶提供電視信號。例如：給一個節(jié)點傳輸信息的花費太大，而他愿意的付款也很少時，網(wǎng)絡(luò)公司可能選擇不給他轉(zhuǎn)播比賽。寫一個程序，找到一個傳輸方案使最多的用戶能看到轉(zhuǎn)播比賽，且轉(zhuǎn)

8、播的費用不超過所有接收信號用戶的交款。程序名：e輸入格式：輸入文件的第一行包含兩個整數(shù) N 和 M(2=N=3000,1=M0 表示走廊通向的展覽廳內(nèi)有 x 幅畫,接下來 x 對整數(shù)(w,c)表示偷一幅價值為 w 的畫需要 c 秒的時間。若 x=0 表示走廊一分為二。(t，c5; x30)輸入是按深度優(yōu)先給出的。房間和走廊數(shù)不超過 300 個。輸出格式：僅一個整數(shù)，表示能獲得的最大價值。輸入樣例：505 0 10 1 10 1 5 0 10 2 500 1 1000 2輸出樣例：1500來源：改編七、河流幾乎整個 Byand 王國都被森林和河流所覆蓋。小點的河匯聚到一起，形成了稍大點的河。就這

9、樣，所有的河水都匯聚并流進(jìn)了一條大河，最后這條大河流進(jìn)了大海。這條大河的入?？谔幱幸粋€村莊名叫 Bytetown.在 Byand 國，有 n 個伐木的村莊，這些村莊都座落在河邊。目前在 Bytetown，有一個巨大的伐木場，它處理著砍下的所有木料。木料被砍下后，順著河流而被運到Bytetown 的伐木場。Byand 的國王決定，為了減少木料的費用，再額外地建造 k個伐木場。這 k 個伐木場將被建在其他村莊里。這些伐木場建造后，木料就不用都被送到Bytetown 了，它們可以在過程中第一個碰到的新伐木場被處理。顯然，如果伐木場座落的那個村子就不用再付運送木料的費用了。它們可以直接被本村的伐木場處

10、理。注：所有的河流都不會分叉，形成一棵樹，根結(jié)點是 bytetown。國王的大臣計算出了每個村子每年要產(chǎn)多少木料，你的任務(wù)是決定在哪些村子建設(shè)伐木場能獲得最小的運費。其中運費的計算方法為：每一噸木料每千米 1 分錢。編一個程序：從文件讀入村子的個數(shù)，另外要建設(shè)的伐木場的數(shù)目，每年每個村子產(chǎn)的木料的塊數(shù)以及河流的描述。計算最小的運費并輸出。程序名：river輸入格式：第一行 包括兩個數(shù) n（2=n=100），k（1=k=50,且 k=n）。n 為村莊數(shù)，k 為要建的伐木場的數(shù)目。除了 bytetown 外，每個村子依次被命名為 1，2，3n，bytetown被命名為 0。接下來 n 行，每行 3 個整數(shù)wi每年 i 村子產(chǎn)的木料的塊數(shù) （0=wi=10000）vi離 i 村子下游最近的村子（即 i 村子的父結(jié)點）（0