CF1207C.Gas Pipeline
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are responsible for installing a gas pipeline along a road. Let's consider the road (for simplicity) as a segment [0,n] on OX axis. The road can have several crossroads, but for simplicity, we'll denote each crossroad as an interval (x,x+1) with integer x . So we can represent the road as a binary string consisting of n characters, where character 0 means that current interval doesn't contain a crossroad, and 1 means that there is a crossroad.
Usually, we can install the pipeline along the road on height of 1 unit with supporting pillars in each integer point (so, if we are responsible for [0,n] road, we must install n+1 pillars). But on crossroads we should lift the pipeline up to the height 2 , so the pipeline won't obstruct the way for cars.
We can do so inserting several zig-zag-like lines. Each zig-zag can be represented as a segment [x,x+1] with integer x consisting of three parts: 0.5 units of horizontal pipe + 1 unit of vertical pipe + 0.5 of horizontal. Note that if pipeline is currently on height 2 , the pillars that support it should also have length equal to 2 units.
Each unit of gas pipeline costs us a bourles, and each unit of pillar — b bourles. So, it's not always optimal to make the whole pipeline on the height 2 . Find the shape of the pipeline with minimum possible cost and calculate that cost.
Note that you must start and finish the pipeline on height 1 and, also, it's guaranteed that the first and last characters of the input string are equal to 0.
输入格式
The fist line contains one integer T ( 1≤T≤100 ) — the number of queries. Next 2⋅T lines contain independent queries — one query per two lines.
The first line contains three integers n , a , b ( 2≤n≤2⋅105 , 1≤a≤108 , 1≤b≤108 ) — the length of the road, the cost of one unit of the pipeline and the cost of one unit of the pillar, respectively.
The second line contains binary string s ( ∣s∣=n , si∈{0,1} , s1=sn=0 ) — the description of the road.
It's guaranteed that the total length of all strings s doesn't exceed 2⋅105 .
输出格式
Print T integers — one per query. For each query print the minimum possible cost of the constructed pipeline.
输入输出样例
输入#1
4 8 2 5 00110010 8 1 1 00110010 9 100000000 100000000 010101010 2 5 1 00
输出#1
94 25 2900000000 13
说明/提示
The optimal pipeline for the first query is shown at the picture above.
The optimal pipeline for the second query is pictured below:
The optimal (and the only possible) pipeline for the third query is shown below:
The optimal pipeline for the fourth query is shown below: