Gas Pipeline (Codeforces 1207C)
Tags: Greedy, dp

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.

Input: The fist line contains one integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of queries. Next $$$2 \cdot T$$$ lines contain independent queries — one query per two lines.The first line contains three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le a \le 10^8$$$, $$$1 \le b \le 10^8$$$) — 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$$$, $$$s_i \in \{0, 1\}$$$, $$$s_1 = s_n = 0$$$) — the description of the road.It's guaranteed that the total length of all strings $$$s$$$ doesn't exceed $$$2 \cdot 10^5$$$.

Output: Print $$$T$$$ integers — one per query. For each query print the minimum possible cost of the constructed pipeline.

Note: 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:  

Sample Inputs:
4
8 2 5
00110010
8 1 1
00110010
9 100000000 100000000
010101010
2 5 1
00

Sample Outputs:
94
25
2900000000
13

Solution (Python):
def solve(l, road):
    a = l[1]
    b = l[2]
    pipes = l[0] + 2
    pillers = l[0] - 1 + len(road)
    res = 0
    if len(road) == 1:
        size = len(road[0])
        return size * a + (size + 1) * b
    for peace in road:
        if len(peace) > 0:
            pillers += 1
    res += a * pipes + b * pillers
    for i in range(1, len(road) - 1):
        size = len(road[i])
        if size > 1:
            res += min((size - 1) * b, 2 * a)
    return res
for _ in range(int(input())):
    print(solve([int(n) for n in input().split()], input().split('1')))

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, a, b) = readInts()
    s = [int(v) for v in readStr()]
    ans = n * a + (n + 1) * b
    if 1 not in s:
        return ans
    else:
        ans += 2 * a
    (lo, hi) = (0, n - 1)
    while lo < n and s[lo] == 0:
        lo += 1
    while lo < hi and s[hi] == 0:
        hi -= 1
    cnt0 = cnt1 = 0
    for i in range(lo, hi + 1):
        if s[i] == 0:
            cnt0 += 1
            if cnt1:
                ans += b * (cnt1 + 1)
                cnt1 = 0
        else:
            cnt1 += 1
            if cnt0:
                ans += min(2 * a, (cnt0 - 1) * b)
                cnt0 = 0
    ans += b * (cnt1 + 1)
    return ans
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys, os
from math import sqrt, gcd, ceil, log, floor, sin, pi
from math import factorial as fact
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
from itertools import permutations
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))
MOD = 10 ** 9 + 7

def main():
    ans_ = []
    for _ in range(int(input())):
        (n, a, b) = read()
        s = input().strip()
        sm = n * a + (n + 1) * b
        arr = [len(j) for j in s.split('0') if j]
        for i in arr:
            sm += (i + 1) * b
        sm += s.count('01') * a + s.count('10') * a
        arr = [len(j) for j in s.strip('0').split('1') if j]
        for i in arr:
            (x, y) = (2 * a + b * (i - 1), 2 * b * (i - 1))
            if x > y:
                sm -= x
                sm += y
        ans_.append(sm)
    for i in ans_:
        print(i)
if __name__ == '__main__':
    main()
''