Remove the Bracket (Codeforces 1787C)
Tags: Greedy, dp

RSJ has a sequence $$$a$$$ of $$$n$$$ integers $$$a_1,a_2, \ldots, a_n$$$ and an integer $$$s$$$. For each of $$$a_2,a_3, \ldots, a_{n-1}$$$, he chose a pair of non-negative integers $$$x_i$$$ and $$$y_i$$$ such that $$$x_i+y_i=a_i$$$ and $$$(x_i-s) \cdot (y_i-s) \geq 0$$$.Now he is interested in the value $$$$$$F = a_1 \cdot x_2+y_2 \cdot x_3+y_3 \cdot x_4 + \ldots + y_{n - 2} \cdot x_{n-1}+y_{n-1} \cdot a_n.$$$$$$Please help him find the minimum possible value $$$F$$$ he can get by choosing $$$x_i$$$ and $$$y_i$$$ optimally. It can be shown that there is always at least one valid way to choose them.

Input: Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$, $$$s$$$ ($$$3 \le n \le 2 \cdot 10^5$$$; $$$0 \le s \le 2 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$).It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print the minimum possible value of $$$F$$$.

Note: In the first test case, $$$2\cdot 0+0\cdot 1+0\cdot 3+0\cdot 4 = 0$$$.In the second test case, $$$5\cdot 1+2\cdot 2+2\cdot 2+1\cdot 5 = 18$$$.

Sample Inputs:
10
5 0
2 0 1 3 4
5 1
5 3 4 3 5
7 2
7 6 5 4 3 2 1
5 1
1 2 3 4 5
5 2
1 2 3 4 5
4 0
0 1 1 1
5 5
4 3 5 6 4
4 1
0 2 1 0
3 99999
200000 200000 200000
6 8139
7976 129785 12984 78561 173685 15480

Sample Outputs:
0
18
32
11
14
0
16
0
40000000000
2700826806

Solution (Python):
for _ in range(int(input())):
    (n, s) = map(int, input().split())
    a = [*map(int, input().split())]
    (min_cost_x, min_cost_y) = (0, 0)
    (prev_x, prev_y) = (a[0], a[0])
    for i in a[1:n - 1]:
        [x, y] = [0, i] if s > i else [i - s, s]
        (min_cost_x, min_cost_y) = (min(min_cost_x + prev_y * x, min_cost_y + prev_x * x), min(min_cost_x + prev_y * y, min_cost_y + prev_x * y))
        (prev_x, prev_y) = (x, y)
    print(min(min_cost_x + y * a[-1], min_cost_y + x * a[-1]))

Solution (Python):
for _ in range(int(input())):
    (n, s) = map(int, input().split())
    a = [*map(int, input().split())]
    (fx, fy) = (0, 0)
    (px, py) = (a[0], a[0])
    for i in a[1:n - 1]:
        [x, y] = [0, i] if s > i else [i - s, s]
        (fx, fy) = (min(fx + py * x, fy + px * x), min(fx + py * y, fy + px * y))
        (px, py) = (x, y)
    print(min(fx + y * a[-1], fy + x * a[-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, s) = readInts()
    arr = readList()
    (dp0, dp1) = (arr[-1] * max(arr[-2] - s, 0), arr[-1] * min(s, arr[-2]))
    for i in range(n - 2, 1, -1):
        (v0, v1) = (arr[i] - max(arr[i] - s, 0), arr[i] - min(s, arr[i]))
        ndp0 = min(dp0 + v0 * max(arr[i - 1] - s, 0), dp1 + v1 * max(arr[i - 1] - s, 0))
        ndp1 = min(dp0 + v0 * min(s, arr[i - 1]), dp1 + v1 * min(s, arr[i - 1]))
        (dp0, dp1) = (ndp0, ndp1)
    (v0, v1) = (arr[1] - max(arr[1] - s, 0), arr[1] - min(s, arr[1]))
    return min(dp0 + v0 * arr[0], dp1 + v1 * arr[0])
for _ in range(int(input())):
    print(solve())