b318: 昏睡紅茶(2)
標籤 : DP Trapping rain water Two pointers 接雨水問題
通過比率 : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2025-10-05 19:32

內容

就在挑選好最大的杯子後,野獸先輩正要端上一杯杯的昏睡紅茶給顧客享用,然而先輩手一滑讓杯子掉到地上碎掉了,在悲痛欲絕的同時,他僥倖希望仍有一些紅茶留下來,趴下身子發現碎掉的玻璃有著高低分布,其中低窪處留下了紅茶。

先輩發現碎掉的玻璃共構成長度為$n$而高度不一的形狀,先輩想要知道最多有多少紅茶剩下來,所以需要你的幫忙去找出低窪處最多能裝多少紅茶。舉例,有長度為6的一串玻璃,其中高度分別為[4,2,0,3,2,5],根據下圖可以發現能裝的紅茶大小為9,也就是最多的紅茶。

輸入說明

輸入的第一行有一正整數$T$,代表接下來有$T$行的測資

每一行(測資)第一個整數為$k$,代表該測資玻璃長度,接下來有$k$個整數$a_i$代表玻璃碎片高度

輸出說明

輸出每筆測資中所剩最大紅茶數量,每筆測資佔一行

範例輸入
2
12 0 1 0 2 1 0 1 3 2 1 2 1
6 4 2 0 3 2 5
範例輸出
6
9
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 0.1s , <1M
提示 :

$1\leq T\leq 10$

$2\leq k\leq 2\times 10^4$

$0\leq a_i\leq 10^5$

標籤:
DP Trapping rain water Two pointers 接雨水問題
出處:
[管理者:
Bai_Yuan_Chen (陳柏源Ronnie)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」