Rudolf and k Bridges (Codeforces 1941E)
Tags: DP, two pointers

Bernard loves visiting Rudolf, but he is always running late. The problem is that Bernard has to cross the river on a ferry. Rudolf decided to help his friend solve this problem.The river is a grid of $$$n$$$ rows and $$$m$$$ columns. The intersection of the $$$i$$$-th row and the $$$j$$$-th column contains the number $$$a_{i,j}$$$ — the depth in the corresponding cell. All cells in the first and last columns correspond to the river banks, so the depth for them is $$$0$$$.  The river may look like this. Rudolf can choose the row $$$(i,1), (i,2), \ldots, (i,m)$$$ and build a bridge over it. In each cell of the row, he can install a support for the bridge. The cost of installing a support in the cell $$$(i,j)$$$ is $$$a_{i,j}+1$$$. Supports must be installed so that the following conditions are met:  A support must be installed in cell $$$(i,1)$$$;  A support must be installed in cell $$$(i,m)$$$;  The distance between any pair of adjacent supports must be no more than $$$d$$$. The distance between supports $$$(i, j_1)$$$ and $$$(i, j_2)$$$ is $$$|j_1 - j_2| - 1$$$. Building just one bridge is boring. Therefore, Rudolf decided to build $$$k$$$ bridges on consecutive rows of the river, that is, to choose some $$$i$$$ ($$$1 \le i \le n - k + 1$$$) and independently build a bridge on each of the rows $$$i, i + 1, \ldots, i + k - 1$$$. Help Rudolf minimize the total cost of installing supports.

Input: The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^3)$$$ — the number of test cases. The descriptions of the test cases follow.The first line of each test case contains four integers $$$n$$$, $$$m$$$, $$$k$$$, and $$$d$$$ ($$$1 \le k \le n \le 100$$$, $$$3 \le m \le 2 \cdot 10^5$$$, $$$1 \le d \le m$$$) — the number of rows and columns of the field, the number of bridges, and the maximum distance between supports.Then follow $$$n$$$ lines, $$$i$$$-th line contains $$$m$$$ positive integers $$$a_{i, j}$$$ ($$$0 \le a_{i, j} \le 10^6$$$, $$$a_{i, 1} = a_{i, m} = 0$$$) — the depths of the river cells.It is guaranteed that the sum of $$$n \cdot m$$$ for all sets of input data does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single number — the minimum total cost of supports installation.

Note: In the first test case, it is most profitable to build a bridge on the second row.  It is not a top view, but side view: gray cells — bridge itself, white cells are empty, black cells — supports, blue cells — water, brown cells — river bottom. In the second test case, it is most profitable to build bridges on the second and third rows. The supports will be placed in cells $$$(2, 3)$$$, $$$(3, 2)$$$, and on the river banks.In the third test case the supports can be placed along the river banks.

Sample Inputs:
5
3 11 1 4
0 1 2 3 4 5 4 3 2 1 0
0 1 2 3 2 1 2 3 3 2 0
0 1 2 3 5 5 5 5 5 2 0
4 4 2 1
0 3 3 0
0 2 1 0
0 1 2 0
0 3 3 0
4 5 2 5
0 1 1 1 0
0 2 2 2 0
0 2 1 1 0
0 3 2 1 0
1 8 1 1
0 10 4 8 4 4 2 0
4 5 3 2
0 8 4 4 0
0 3 4 8 0
0 8 1 10 0
0 10 1 5 0

Sample Outputs:
4
8
4
15
14

Solution (Python):
import sys
from collections import deque

def solve():
    (n, m, l, d) = map(int, input().split())
    river = [list(map(int, input().split())) for _ in range(n)]
    ans = [0] * n
    for i in range(n):
        dp = [0] * m
        dp[0] = 1
        q = deque([0])
        for j in range(1, m):
            while abs(q[0] - j) - 1 > d:
                q.popleft()
            dp[j] = dp[q[0]] + river[i][j] + 1
            while q and dp[q[-1]] >= dp[j]:
                q.pop()
            q.append(j)
        ans[i] = dp[m - 1]
    s = sum(ans[:l])
    fans = s
    for i in range(l, n):
        s -= ans[i - l]
        s += ans[i]
        fans = min(fans, s)
    print(fans)
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()

Solution (Python):
from collections import deque
from math import inf
import sys
input = lambda : sys.stdin.readline().strip()

def solve():
    (n, m, k, d) = map(int, input().split())
    ls = []
    total = 0
    ans = inf
    for j in range(n):
        a = list(map(int, input().split()))
        dp = [0] * m
        dp[0] = 1
        q = deque()
        for i in range(1, m):
            while len(q) and dp[i - 1] < dp[q[-1]]:
                q.pop()
            q.append(i - 1)
            while q[0] < i - d - 1:
                q.popleft()
            dp[i] = a[i] + 1 + dp[q[0]]
        ls.append(dp[m - 1])
        total += dp[m - 1]
        if j >= k - 1:
            ans = min(ans, total)
            total -= ls[j - k + 1]
    print(ans)
for _ in range(int(input())):
    solve()

Solution (Python):
from collections import deque
for _ in range(int(input())):
    (n, m, k, d) = [*map(int, input().split())]
    res = []
    for i in range(n):
        a = [*map(int, input().split())]
        dp = [0] * m
        dp[0] = 1
        q = deque()
        q.append(0)
        for j in range(1, m):
            dp[j] = a[j] + 1 + dp[q[0]]
            while q and dp[q[-1]] >= dp[j]:
                q.pop()
            q.append(j)
            if j - q[0] > d:
                q.popleft()
        res.append(dp[-1])
    ans = tmp = sum(res[0:k])
    for i in range(n - k):
        tmp = tmp - res[i] + res[i + k]
        ans = min(ans, tmp)
    print(ans)