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

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

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

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

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

[BFS]POI2007 山峰和山谷 grz 解題報告

Ridges and Valleys

Memory limit: 32 MB

Byteasar loves trekking in the hills. During the hikes he explores all the ridges and valleys in vicinity. Therefore, in order to plan the journey and know how long it will last, he must know the number of ridges and valleys in the area he is going to visit. And you are to help Byteasar.
Byteasar has provided you with a map of the area of his very next expedition. The map is in the shape of a square. For each field belonging to the square (for ), its height is given.
We say two fields are adjacent if they have a common side or a common vertex (i.e. the field is adjacent to the fields , , , , , , , , provided that these fields are on the map).
We say a set of fields forms a ridge (valley) if:

• all the fields in have the same height,
• the set forms a connected part of the map (i.e. from any field in it is possible to reach any other field in while moving only between adjacent fields and without leaving the set ),
• if and the field is adjacent to , then (for a ridge) or (for a valley).

In particular, if all the fields on the map have the same height, they form both a ridge and a valley.
Your task is to determine the number of ridges and valleys for the landscape described by the map.

POI1997 階梯教室設備利用 rez 解題報告

階梯教室設備利用

【問題描述】

我們現有許多演講要在階梯教室中舉行。每一個演講都可以用唯一的起始和終止時間來確定，如果兩個演講時間有部分或全部重複，那麼它們是無法同時在階級教室中舉行的。現在我們想要盡最大可能的利用這個教室，也就是說，我們需要在這些演講中選擇一些不重複的演講來舉行使得他們用的總時間儘可能的長。我們假設在某一演講結束的瞬間我們就可以立即開始另一個演講。

任務：

請寫一個程序：

• 在輸入文件中讀入所有演講的起始和終止時間；

• 計算最大的可能演講總時間；

• 把結果寫到輸出文件中。

【輸入文件】

在輸入文件的第一行包括一個正整數 n ， n <= 10000 ，為所有的演講的數目。

以下的 n 行每行含有兩個由空格隔開整數 p 和 k ， 0 <= p < k <= 30000 。這樣的一對整數表示一個演講由時間 p 開始到時間 k 結束。

【輸出文件】

輸出文件只有唯一的一個整數，為最長的演講總時間。

[搜索]POI1997 阿里巴巴 ali 解題報告

【問題描述】
想要“芝麻開門”，必須擁有一定數量的錢幣，其中包括至少z枚金幣，s枚銀幣和m枚銅幣。 最初，阿里巴巴擁有三種錢幣若干枚。他可以按照一定規則和芝麻之門的守護者進行交易。 每一種規則用以下形式表示：

z1, s1, m1 -> z2, s2, m2 (zi, si, mis屬於集合{0,1,2,3,4})。

這樣一種規則表示阿里巴巴可以將z1枚金幣, s1枚銀幣, m1枚銅幣換成z2枚金幣, s2枚銀幣, m2枚銅幣。 一次交易而得的錢幣可以繼續參加下一次的交易。

任務

從文件中讀入幾組資料；對於每一組資料：

阿里巴巴最初擁有的金銀銅三種錢幣數目

“芝麻開門”所需的金銀銅三種錢幣數目

所有交易規則

對每一組資料，判斷是否存在有限次的交易，使阿里巴巴能開啟芝麻之門。如果是，則將最少交易次數輸出，否則在輸出NIE(波蘭文NO)

把結果寫進文件中

[網絡最大流]POI1999 洞穴探險 gro 解題報告

問題描述

古老的Byte山上有一處神祕的連環洞穴。考古學家們爲了對這個洞穴進行研究，組織了一次探險活動。他們花了幾天的時間仔細地翻閱了前人留下的資料，對該連環洞穴有了大致的瞭解。

這是一個有許多不同的小溶洞組成的連環洞穴，每個小溶洞都分佈在不同的地層中，並且可能通過洞穴隧道與其他小溶洞相通。

考古學家們已經發現了作爲連環洞穴的入口的一個小溶洞，並且根據前人的資料，繪製出了洞穴的地圖，標明瞭哪些小溶洞之間是有洞穴隧道相連的。

富有冒險和激情的考古學家們都期望自己能夠獨自進行探險活動。於是，他們又提出了這樣的要求：從入口的溶洞出發時，每個人都選擇一條不同的 洞穴隧道前進；探險結束時，每個人都是通過不同的洞穴隧道抵達最底層的小溶洞。當然了，這些考古學家也達成了妥協：在探險的過程中，可以有不止一名的考古 學家通過同一條洞穴隧道。 爲了體現這次探險活動的一往直前的精神，考古學家們還決定，要從小溶洞入口進入，一直抵達最底層的溶洞！每個考古學家探險路線上通過的小溶洞所在的地層必 須比該路線上前一個溶洞的地層低。

考古學家提出來如此多的要求使得本次探險活動的組織者犯了愁，他究竟最多能邀請多少位考古學家來參加這項活動呢？