{"problem":{"name":"「Daily OI Round 4」Snow","description":{"content":"下雪了，小 Y 堆了 $n$ 个雪柱排成一排，调皮的小 X 打算推倒这 $n$ 个雪柱，他想在最少的时间内推倒所有雪柱，于是他请你来为他出谋划策。 小 Y 堆的每个雪柱高 $a_i$ 单位，推倒一个雪柱的时间为该雪柱的高度。小 X 只能从这一排雪柱的两端推雪柱 \\*，次数不限，小 X 移动的时间可以忽略不计。这样就可以使一个雪柱倒向其他雪柱，从而击倒另一个雪柱（击倒的时间忽略不计），然后发生连锁","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10569"},"statements":[{"statement_type":"Markdown","content":"下雪了，小 Y 堆了 $n$ 个雪柱排成一排，调皮的小 X 打算推倒这 $n$ 个雪柱，他想在最少的时间内推倒所有雪柱，于是他请你来为他出谋划策。\n\n小 Y 堆的每个雪柱高 $a_i$ 单位，推倒一个雪柱的时间为该雪柱的高度。小 X 只能从这一排雪柱的两端推雪柱 \\*，次数不限，小 X 移动的时间可以忽略不计。这样就可以使一个雪柱倒向其他雪柱，从而击倒另一个雪柱（击倒的时间忽略不计），然后发生连锁反应，更加节省时间 \\*\\*。\n\n设初始的势能为当前手动推倒的雪柱 $k$ 的高度 $p=a_k$，则此轮连锁反应中第 $i$ 个雪柱倒向第 $j$ 个雪柱时：\n\n- 若 $p\\ge a_j$，则使第 $j$ 个雪柱也被击倒，并令 $p \\gets a_j$。\n- 若 $p< a_j$，则第 $j$ 个雪柱的高度减少（不被击倒），终止整个连锁反应，令 $a_j \\gets a_j-p$。\n\n请你求出推倒所有雪柱的最短时间。\n\n\\*：每一次要么从左边推最左边的雪柱，要么从右边推最右边的雪柱。\n\n\\*\\*：雪柱的倒塌方向取决于推雪柱的方向，如果从左边推，雪柱就会向右依次倒塌（第 $i$ 个雪柱倒塌向第 $i+1$ 个雪柱），反之同理。\n\n## Input\n\n**本题有多组测试数据。**\n\n第一行一个整数 $T$，表示数据组数。\n\n对于每组数据：\n \n第一行一个整数 $n$，表示雪柱的数量。\n\n第二行 $n$ 个整数，分别表示每个雪柱的高度。\n\n## Output\n\n对于每组数据：输出一行一个整数，表示推倒所有雪柱的最短时间。\n\n[samples]\n\n## Note\n\n#### 【样例解释】\n\n- **对于第一组数据：**\n\n> 第一次从左边推，耗费 $2$ 点时间，使得 $5$ 个雪柱 的高度分别变为：$0,1,1,4,5$。 \n>\n> 第二次从右边推，耗费 $5$ 点时间，使得所有雪柱都被击倒。 \n>\n> 共耗费 $7$ 点时间。\n\n- **对于第二组数据：**\n\n> 从左边或者右边都可以一次性推完，共耗费 $6$ 点时间。\n\n- **对于第三组数据：**\n\n> 第一次从右边推，耗费 $4$ 点时间，使得 $6$ 个雪柱的高度分别变为：$1,1,4,4,0,0$。  \n>\n> 第二次从右边推，耗费 $4$ 点时间，使得所有雪柱都被击倒。\n>\n> 共耗费 $8$ 点时间。\n\n#### 【数据范围】\n  \n**本题采用捆绑测试。**\n\n|$\\text{Subtask}$|分值|$n \\le$|\n| :-----------: | :-------------:|:-----------: |\n|$0$|$10$|$20$|\n|$1$|$15$|$100$|\n|$2$|$25$|$1000$|\n|$3$|$50$|$10^5$|\n\n对于全部数据，保证：$1 \\le T \\le 10$，$1 \\le n \\le 10^5$，$1 \\le a_i \\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10569","tags":["贪心","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3\n5\n2 3 1 4 5\n6 \n6 6 6 6 6 6\n6\n1 1 4 5 1 4","7\n6\n8"]],"created_at":"2026-03-03 11:09:25"}}