#P1409. 2023.07.29-KDXF-开发岗-第一题-企鹅
2023.07.29-KDXF-开发岗-第一题-企鹅
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
现在有一个警察抓小偷的游戏,塔子哥刚好玩到让小偷跑到了一个长长的桥面上去。
假设在桥面上,有N块紧密相连的桥板。标号1~N,小偷已经逃到了标号为K的桥板上。现在, 塔子哥可以用超能力拆除一些桥板来使得小偷掉落河中,然而他无法拆除小偷所踩的桥板K。每个桥板拆除时都需要支付不同的代价Ai,当桥体两侧的桥板都没有与河两岸连接时,则桥和小偷会一起掉落到河中。
求塔子哥需要支付的最小代价。
假设某一情况如图:
8 | 小偷 | 7 | 3 | 6 |
---|
桥体1和桥体4可以通过分别支付8和3的代价来拆除,此时小偷所在的桥板2和桥板3一起掉落河中。因此最小代价为11.
第一行给出N, 表示冰块的数量。 第二行中,按顺序给出代表打破第i块冰块所需的力的Ai。 题目保证企鹅所在的地方用−1表示, 没有企鹅位于冰块1或冰块N的情况。 3≤N≤2∗105,1≤Ai≤109
输出可以将企鹅击落到水中的最小力。
输入
5
8 -1 7 3 6
输出
11
说明
见题目举例
输入
10
49 46 -1 55 54 53 52 51 50 51
输出
96
说明 打破桥面2和桥面9, 最小代价为46+50=96
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.