c244: 來自深淵【序】尋寶記
Tags : 分類窮舉 暴力求解法
Accepted rate : 7人/52人 ( 13% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-08-10 22:33

Content

阿比斯

三千九百年前位於西海貝奧魯斯卡的某孤島上

發現直徑約10000KM的巨形深淵

其深淵有著某未知反重力場 想知道深淵裡更多的秘密 只能親身下去探索

深淵的詛咒

自深界一層「阿比斯之淵」返回 - 輕微的暈眩及嘔吐

自深界二層「誘惑之森」返回 - 嚴重的作嘔、頭疼及四肢麻痺

自深界三層「大斷層」返回 - 平衡感異常、幻聽、幻覺

自深界四層「巨人之杯」返回 - 渾身劇烈疼痛、全身孔洞流血

自深界五層「亡骸之海」返回 - 喪失所有感覺、意識混亂、自殘行為

自深界六層「來無回之都」返回 - 喪失人體機能、瀕死狀態

自深界七層「最終極之渦」返回 - 直接死亡

日常

有一位見習赤笛少女 RIKO 是傳說中探窟家白笛「殲滅之萊莎」的女兒

某天巧遇了一個Robot 雷格便一起了冒險

同時,為了見到在深界六層「來無回之都」的母親,他們踏上了前往深淵深層的旅途

有天Riko走到了深界一層「阿比斯之淵」的一處角落,發現了遺物「月玉」和一個閃閃發亮的東西

RIKO:「啊!!!這是甚麼好漂亮~」

雷格:「星屑」

RIKO:「我要通通帶走!」

 

雷格一抬頭就看見一個巨大的石頭

不對,是一個趴在地上被背包壓著的貪心小女孩

她還依稀記得這些遺物可以賣出的銀幣

所以,他決定在最喜歡的兩樣東西各挑一些

希望可以換得一堆銀幣

RIKO究竟能帶走多少呢~

Input

第一行輸入T
然後有T行,每行有5個數字 N,s1,v1,s2,v2


依序代表RIKO背包的容量,第一樣東西的體積,價錢 ,第二樣東西的體積,價錢

Output

輸出帶走的總價值

Sample Input
2
100 1 1 2 3
100 34 34 5 3
Sample Output
Case #1: 150
Case #2: 86
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (8%): 0.1s , <1M
不公開 測資點#1 (10%): 0.1s , <1M
不公開 測資點#2 (10%): 0.1s , <1M
不公開 測資點#3 (12%): 0.3s , <10M
不公開 測資點#4 (15%): 0.3s , <10M
不公開 測資點#5 (15%): 0.5s , <10M
不公開 測資點#6 (15%): 0.5s , <10M
不公開 測資點#7 (15%): 1.5s , <1M
Hint :

19/08/10 題目內容不變,更動所有測資及範圍  [如果日後發現時限壓太緊的話會再調整]

 如果測資有誤or測資太弱歡迎寫信給我

 測資點 #0  T=100,1≤N,s1,v1,s2,v2≤100。
 測資點 #1  T=100,N=1000,1≤s1,v1,s2,v2≤N。
 測資點 #2  T=1,000,1≤N≤230,1≤s1,v1,s2,v2≤N。
 測資點 #3  T=100,000,N=230,1≤s1,v1,s2,v2≤N。
 測資點 #4  T=100,000,N=230,1≤s1,s2≤100,1≤v1,v2≤N。
 測資點 #5  T=100,000,N=230,1≤s1≤100,1≤s2,v1,v2≤N。
 測資點 #6  T=100,000,N=230,1≤s2≤100,1≤s1,v1,v2≤N。
 測資點 #7  T=5,000,N=230,1≤s1,s2,v1,v2≤N。

 

範例測資:

測資#1: 第二樣東西50個 3*50=150

測資#2: 第一樣東西2個 + 第二樣東西6個 2*34+6*3=86 背包空間: 98/100

 

如果用cin, cout 可改用scanf, printf 或以下優化

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

不需要一些奇奇怪怪的IO優化,想辦法根據測資的範圍來降低窮舉的次數

Tags:
分類窮舉 暴力求解法
出處:
106學年度板橋高中校內資訊學科能力競賽310573sao [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
12744
310573sao (Jiburiru)
c244
算法優化
708 2017-09-23 09:01