[動態規劃]OI練習題 週年紀念聚會 aniv 解題報告

週年紀念聚會

Background

校長正在籌備學校的80週年紀念聚會。由於學校的職員有不同的職務級別，可以構成一棵以校長為根的人事關係樹。每個職員都有一個唯一的整數編號（範圍在1到N之間），並且對應一個參加聚會所獲得的歡樂度。為了使每個參加聚會者都感到歡樂，校長想設法使每個職員和他（她）的直接上司不會同時參加聚會。

Problem

你的任務是設計一份參加聚會者的名單，使總的歡樂度最高。

Input

輸入的第一行是一個整數N，1<= N <= 6000

以下的N行是對應的N個職員的歡樂度（歡樂度是一個從-128到127之間的整數）

接著是學校的人事關係樹，樹的每一行格式如下：

<L> <K>

表示第K個職員是第L個職員的直接上司。

輸入以0 0表示結束

輸出：參加聚會者獲得的最大總歡樂度

[動態規劃]OI練習題 最後的利益 9cwy 解題報告

【問題描述】
最近9C馬上就要和WY交收WOW的運營權了，9C為了最後的利益決定讓GM控制玩家上線時間。因為9C的小霸王伺服器總是容易爆滿，所以某伺服器中只剩一個玩家的位子，GM為了讓玩家在線時間總和最長。他將選擇一些上線時間不重複的玩家讓他們上線。我們假設某玩家下線以後，另一個玩家可以立即登入。但是GM又笨又懶，他希望你能幫他幫他寫一個程序來完成這個任務。

【輸入文件】

輸入文件第一行是一個正整數n，n<=10000，為玩家數量

一下n行每行含有兩個數t1、t2表示某玩家上線時段

【輸出文件】

輸出最長遊戲總時間

[動態規劃]POI 1998 ple 潛水員問題 解題報告

【問題描述】
     一個潛水員在潛水時使用一種特殊的裝置：一個有兩個容器的氣筒。一個容器中裝的是氧氣，另一個容器中裝氮氣。潛水員需要攜帶的氧氣和氮氣量依賴於潛水的時間和深度。潛水員有一系列的氣筒，用來在不同的情況下攜帶。每個氣筒可以用這樣幾個量來描述：氣筒的質量，氣筒中所能容納的氧氣量，以及可以容納的氮氣量。為了能完成最近的一個任務，潛水員需要一定量的氧氣和氮氣。潛水員有一系列準備好的氣筒。他希望能攜帶總質量儘可能小的氣筒下水。現在請你幫他計算一下至少要攜帶多少質量的氣筒下水才能完成這個任務。

【示例說明】
潛水員有以下 5 個氣筒。每個氣筒用三個整數來描述：氣筒所能容納的氧氣的量，氮氣的量和氣筒的質量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果這次任務中潛水員需要攜帶 5 升 氧氣， 60 升 氮氣。那麼他至少要攜帶總質量為 249 的氣筒下水（樣例中的第一個和第二個氣筒或者第四個和第五個氣筒）。

[計算幾何]USACO Feb08 USACO Silver Game of Lines 連線遊戲

Title: 連線遊戲

Input: lines.in

Output: lines.out

Time Limit: 1000 ms

Memory Limit: 16 MB

Level: ★☆

Farmer John最近發明瞭一個遊戲，來考驗自命不凡的貝茜。遊戲開始的時候，FJ會給貝茜一塊畫著N (2 <= N <= 200)個不重合的點的木板，其中第i個點的橫、縱座標分別為X_i和Y_i (-1,000 <= X_i <=1,000；-1,000 <= Y_i <= 1,000)。

貝茜可以選兩個點畫一條過它們的直線，當且僅當平面上不存在與畫出直線平行的直線。遊戲結束時貝茜的得分，就是她畫出的直線的總條數。為了在遊戲中勝出，貝茜找到了你，希望你幫她計算一下最大可能得分。

程序名: lines

[多源最短路]USACO 奶牛聚會 spart

譯: zqzas

N(1 ≤ N ≤ 1000)個農場中的每個農場都有一隻奶牛去參加位於第X個農場的聚會.共有M (1 ≤ M ≤ 100,000)條單向的道路,每條道路連接一對農場.通過道路i會花費Ti (1 ≤ Ti ≤ 100)的時間.

作爲參加聚會的奶牛必須走到聚會的所在地(農場X).當聚會結束時,還要返回各自的農場.奶牛都是很懶的,她們想找出花費時間最少的路線.由於道路都是單向的,所有她們前往農場X的路線可能會不同於返程的路線.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back? 對於所有參加聚會的奶牛,找出前往聚會和返程花費總時間最多的奶牛,輸出這隻奶牛花費的總時間.

[次短路徑]HAOI2005 路由選擇問題 route 解題報告

路由選擇問題

【問題描述】

    X城有一個含有N個節點的通信網絡，在通信中，我們往往關心資訊從一個節點I傳輸到節點J的最短路徑。遺憾的是，由於種種原因，線路中總有一些節點會出故障，因此在傳輸中要避開故障節點。

任務一：在己知故障節點的情況下，求避開這些故障節點，從節點I到節點J的最短路徑S0。

任務二：在不考慮故障節點的情況下，求從節點I到節點J的最短路徑S1、第二最短路徑S2。

【輸入文件】

第1行： N I J (節點個數 起始節點 目標節點)

第2—N+1行： Sk1 Sk2…SkN (節點K到節點J的距離爲SkJ K=1，2，……，N)

最後一行： P T1 T2……Tp (故障節點的個數及編號)

【輸出文件】

S0 S1 S2 (S1<=S2 從節點I到節點J至少有兩條不同路徑)