【正文】 備。他有一個(gè)帶 2種氣體的氣缸：一個(gè)為氧氣，一個(gè)為氮?dú)?。讓潛水員下潛的深度需要各種的數(shù)量的氧和氮。潛水員有一定數(shù)量的氣缸。每個(gè)氣缸都有重量和氣體容量。潛水員為了完成他的工作需要特定數(shù)量的氧和氮。他完成工作所需氣缸的總重的最低限度的是多少？ 例如：潛水員有 5個(gè)氣缸。每行三個(gè)數(shù)字為：氧，氮的（升）量和氣缸的重量： 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 如果潛水員需要 5升的氧和 60升的氮?jiǎng)t總重最小為 249（ 1， 2或者 4， 5號(hào)氣缸）。 你的任務(wù)就是計(jì)算潛水員為了完成他的工作需要的氣缸的重量的最低值。 【 輸入格式 】 第一行有 2整數(shù) t， a（ 1=t=21， 1=a=79）。它們表示氧，氮各自需要的量。 第二行為整數(shù) n （ 1=n=1000）表示氣缸的個(gè)數(shù)。 此后的 n行，每行包括 ti， ai， wi（ 1=ti=21， 1=ai=79， 1=wi=800）3整數(shù)。這些各自是：第 i個(gè)氣缸里的氧和氮的容量及汽缸重量。 【 輸出格式 】 僅一行包含一個(gè)整數(shù)，為潛水員完成工作所需的氣缸的重量總和的最低值。 【 輸入樣例 】 5 60 5 3 36 120 10 25 129 5 50 250 1 45 130 4 20 119 【 輸出樣例 】 249 火車票 【 問(wèn)題描述 】 從 Ekaterinburg到 Sverdlovsk的火車線路上有若干個(gè)站點(diǎn)。這條線路可以近似的表示為一條線段，火車站就是線段上的點(diǎn)。線路始于 Ekaterinburg，終于Sverdlovsk。 Ekaterinburg被標(biāo)號(hào)為 1， Sverdlovsk被標(biāo)號(hào)為 n。（ n為整條線路上的站點(diǎn)數(shù)） 線路上的任意兩個(gè)站點(diǎn)間的直達(dá)票價(jià)是由它們間的距離決定的，票價(jià)根據(jù)以下規(guī)則制定： X為兩站的距離 價(jià)格 0X=L1 C1 L1X=L2 C2 L2X=L3 C3 如果兩站的間距超過(guò) L3，則無(wú)直達(dá)車票。所以有時(shí)可能有必要買多張票，通過(guò)轉(zhuǎn)車的方式，從一個(gè)站到達(dá)另一個(gè)站。 例如，在上面的圖中，有 7個(gè)站點(diǎn)。 2號(hào)站點(diǎn)到 6號(hào)站點(diǎn)的距離超過(guò) L3，不能買直達(dá)票。存在若干種中轉(zhuǎn)的方法，其中的一種是買兩張票：先花費(fèi) C2從 2號(hào)站到達(dá) 3號(hào)站，然后花費(fèi) C3從 3號(hào)站到 6號(hào)站，一種花費(fèi) C2+C3。 你的任務(wù)是，找出一種最經(jīng)濟(jì)的中轉(zhuǎn)方案。 【 輸入格式 】 從文本文件 。 第一行 6個(gè)整數(shù) L1, L2, L3, C1, C2, C3（ 1=L1L2L3=10^9, 1=C1C2C3=10^9），中間用空格分隔。 第二行一個(gè)整數(shù) n（ 2=n=100），表示線路上的車站數(shù)。 第三行兩個(gè)整數(shù) s和 t，分別是起點(diǎn)和終點(diǎn)的編號(hào)。注意： s不一定小于 t。 以下的 n1行，按據(jù) Ekaterinburg遠(yuǎn)近，每行描述了一個(gè)車站的位置。它包含一個(gè)整數(shù)，表示該車站距 Ekaterinburg的距離。 任意兩個(gè)車站的距離不超過(guò) 10^9，任意兩個(gè)相鄰的車站的距離不超過(guò) L3。 【 輸出格式 】 一個(gè)整數(shù)，表示從給定的一個(gè)站到給定的另一個(gè)站的最小花費(fèi)。 【 輸入樣例 】 3 6 8 20 30 40 7 2 6 3 7 8 13 15 23 【 輸出樣例 】 70 單詞的劃分 【 問(wèn)題描述 】 有一個(gè)很長(zhǎng)的由小寫字母組成字符串。為了便于對(duì)這個(gè)字符串進(jìn)行分析，需要將它劃分成若干個(gè)部分，每個(gè)部分稱為一個(gè)單詞。出于減少分析量的目的，我們希望劃分出的單詞數(shù)越少越好。你就是來(lái)完成這一劃分工作的。 【 輸入格式 】 從文本文件 。 第一行，一個(gè)字符串。（字符串的長(zhǎng)度不超過(guò) 100） 第二行一個(gè)整數(shù) n，表示單詞的個(gè)數(shù)。（ n=100） 第 3~n+2行，每行列出一個(gè)單詞。 【 輸出格式 】 一個(gè)整數(shù)，表示字符串可以被劃分成的最少的單詞數(shù)。 【 輸入樣例 】 realityour 5 real reality it your our 【 輸出樣例 】 2 注：原字符串可拆成 real+it+your或 reality+our，由于reality+our僅為兩個(gè)部分，因此最優(yōu)解為 2，另外注意，單詞列表中的每個(gè)單詞都可以重復(fù)使用多次，也可以不用 饑餓的牛 【 問(wèn)題描述 】 牛在飼料槽前排好了隊(duì)。飼料槽依次用 1到 N(1=N=2022)編號(hào)。每天晚上，一頭幸運(yùn)的牛根據(jù)約翰的規(guī)則，吃其中一些槽里的飼料。 約翰提供 B個(gè)區(qū)間的清單。一個(gè)區(qū)間是一對(duì)整數(shù) startend ，1=start=end=N，表示一些連續(xù)的飼料槽，比如 13,78,34等等。?？梢匀我膺x擇區(qū)間，但是牛選擇的區(qū)間不能有重疊。 當(dāng)然，牛希望自己能夠吃得越多越好。給出一些區(qū)間，幫助這只牛找一些區(qū)間，使它能吃到最多的東西。 在上面的例子中， 13和 34是重疊的；聰明的牛選擇 {13， 78}，這樣可以吃到 5個(gè)槽里的東西。 【 輸入格式 】 第一行，整數(shù) B(1=B=1000) 第 2到 B+1行，每行兩個(gè)整數(shù)，表示一個(gè)區(qū)間，較小的端點(diǎn)在前面。 【 輸出格式 】 僅一個(gè)整數(shù)，表示最多能吃到多少個(gè)槽里的食物。 【 輸入樣例 】 3 1 3 7 8 3 4 【 輸出樣例 】 5 1護(hù)衛(wèi)隊(duì) () 【 問(wèn)題描述 】 護(hù)衛(wèi)車隊(duì)在一條單行的街道前排成一隊(duì)，前面河上是一座單行的橋。因?yàn)榻值朗且粭l單行道，所以任何車輛都不能超車。橋能承受一個(gè)給定的最大承載量。為了控制橋上的交通，橋兩邊各站一個(gè)指揮員。護(hù)衛(wèi)車隊(duì)被分成幾個(gè)組，每組中的車輛都能同時(shí)通過(guò)該橋。當(dāng)一組車隊(duì)到達(dá)了橋的另一端，該端的指揮員就用電話通知另一端的指揮員，這樣下一組車隊(duì)才能開(kāi)始通過(guò)該橋。每輛車的重量是已知的。任何一組車隊(duì)的重量之和不能超過(guò)橋的最大承重量。被分在同一組的每一輛車都以其最快的速度通過(guò)該橋。一組車隊(duì)通過(guò)該橋的時(shí)間是用該車隊(duì)中速度最慢的車通過(guò)該橋所需的時(shí)間來(lái)表示的。問(wèn)題要求計(jì)算出全部護(hù)衛(wèi)車隊(duì)通過(guò)該橋所需的最短時(shí)間值。 【 輸入格式 】 輸入文件第一行包含三個(gè)正整數(shù) (用空格隔開(kāi) )，第一個(gè)整數(shù)表示該橋所能承受的最大載重量 (用噸表示 )；第二個(gè)整數(shù)表示該橋的長(zhǎng)度 (用千米表示 )；第三個(gè)整數(shù)表示該護(hù)衛(wèi)隊(duì)中車輛的總數(shù) (n1000)。接下來(lái)的幾行中，每行包含兩個(gè)正整數(shù) W和 S(用空格隔開(kāi) )， W表示該車的重量 (用噸表示 )， S表示該車過(guò)橋能達(dá)到的最快速度 (用千米 /小時(shí)表示 )。車子的重量和速度是按車子排隊(duì)等候時(shí)的順序給出的。 【 輸出格式 】 輸出文件應(yīng)該是一個(gè)實(shí)數(shù)，四舍五入精確到小數(shù)點(diǎn)后 1位，表示整個(gè)護(hù)衛(wèi)車隊(duì)通過(guò)該橋所需的最短時(shí)間 (用分鐘表示 )。 【 輸入樣例 】 100 5 10 40 25 50 20 50 20 70 10 12 50 9 70 49 30 38 25 27 50 19 70 【 輸出樣例 】 1乘法游戲 【 問(wèn)題描述 】 乘法游戲是在一行牌上進(jìn)行的。每一張牌包括了一個(gè)正整數(shù)。在每一個(gè)移動(dòng)中，玩家拿出一張牌，得分是用它的數(shù)字乘以它左邊和右邊的數(shù)，所以不允許拿第 1張和最后 1張牌。最后一次移動(dòng)后，這里只剩下兩張牌。 你的目標(biāo)是使得分的和最小。 例如，如果數(shù)是 10 1 50 20 5，依次拿 50，總分是 10*1*50+50*20*5+10*50*5=8000 而拿 50、 1，總分是 1*50*20+1*20*5+10*1*5=1150。 【 輸入文件 】 輸入文件 (3=n=100)，第二行包括 N個(gè) 1100的整數(shù)，用空格分開(kāi)。 【 輸出文件 】 輸出文件 ：最小得分 【 樣例輸入 】 6 10 1 50 50 20 5 【 樣例輸出 】 3650 1馬棚問(wèn)題 () 【 問(wèn)題描述 】 每天，小明和他的馬外出，然后他們一邊跑一邊玩耍。當(dāng)他們結(jié)束的時(shí)候，必須帶所有的馬返回馬棚，小明有 K個(gè)馬棚。他把他的馬排成一排然后跟隨它走向馬棚，因?yàn)樗鼈兎浅Ｆ?，小明不想讓他的馬做過(guò)多移動(dòng)。因此他想了一個(gè)方法：將馬按照順序放在馬棚中，后面的馬放的馬棚的序號(hào)不會(huì)大于前面的馬放的馬棚序號(hào)。而且，他不想他的 K個(gè)馬棚中任何一個(gè)空置，也不想任何一匹馬在外面。已知共有黑、白兩種馬，而且它們相處的并不十分融洽。如果有 I個(gè)白馬和 J個(gè)黑馬在一個(gè)馬棚中，那么這個(gè)馬棚的不愉快系數(shù)將是 i*j。所有 K個(gè)馬棚的不愉快系數(shù)的和就是系數(shù)總和。確定一種方法把 n匹馬放入 k個(gè)馬棚，使得系數(shù)總和最小。 【 輸入格式 】 在第一行有兩個(gè)數(shù)字： N（ 1=N=500〉 和 K（ 1=K=N〉 。在接下來(lái)N 行是 N 個(gè)數(shù)。在這些行中的第 I行代表隊(duì)列中的第 I匹馬的顏色： 1意味著馬是黑色， 0意味著馬是白色。 【 輸出格式 】 只輸出一個(gè)單一的數(shù)字，代表系數(shù)總和可能達(dá)到的最小值。 【 輸入樣例 】 6 3 //６匹馬３個(gè)馬棚 1 //第１匹馬為黑馬 1 0 //第３匹馬為白馬 1 0 1 【 輸出樣例 】 2 //最小系數(shù)總和 1滑雪 () 【 問(wèn)題描述 】 小明喜歡滑雪，因?yàn)榛┑拇_很刺激，可是為了獲得速度，滑的區(qū)域必須向下傾斜，當(dāng)小明滑到坡底，不得不再次走上坡或等著直升機(jī)來(lái)載他，小明想知道在一個(gè)區(qū)域中最長(zhǎng)的滑坡。滑坡的長(zhǎng)度由滑過(guò)點(diǎn)的個(gè)數(shù)來(lái)計(jì)算，區(qū)域由一個(gè)二維數(shù)組給出，數(shù)組的每個(gè)數(shù)字代表點(diǎn)的高度。下面是一個(gè)例子： 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)高度減小，在上面的例子中，一條可行的滑坡為 252417161（從 25開(kāi)始到 1結(jié)束），當(dāng)然2524……2…1 更長(zhǎng)，事實(shí)上這是最長(zhǎng)的一條。 【 輸入格式 】 輸入的第一行為表示區(qū)域的二維數(shù)組的行數(shù) R和列數(shù) C（ 1≤R、 C≤100）下面是 R行，每行有 C個(gè)數(shù)代表高度。 【 輸出格式 】 輸出區(qū)域中最長(zhǎng)的滑坡長(zhǎng)度。 [i1,j]↓ [i,j1]→ [i,j] ←[i,j+1] [i+1,j]↑