311149: CF1941E. Rudolf and k Bridges
Description
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.
InputThe 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$.
OutputFor each test case, output a single number — the minimum total cost of supports installation.
ExampleInput5 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 0Output
4 8 4 15 14Note
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.
Output
输入数据格式：第一行包含一个整数t，表示测试用例的数量。每个测试用例的第一行包含四个整数n、m、k和d，分别表示网格的行数、列数、建桥的数量和支撑间的最大距离。接下来的n行，每行包含m个正整数，表示河的深度。
输出数据格式：对于每个测试用例，输出一个数字，表示安装支撑的最小总成本。
LaTeX格式：
\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{listings}
\usepackage{xcolor}
\title{E. Rudolf and k Bridges}
\author{}
\date{}
\begin{document}
\maketitle
\section{Problem Statement}
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 \textbf{first} and \textbf{last} columns correspond to the river banks, so the depth for them is $ 0 $.
\begin{center}
\includegraphics[width=0.5\textwidth]{espresso}
\end{center}
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:
\begin{enumerate}
\item A support must be installed in cell $ (i,1) $;
\item A support must be installed in cell $ (i,m) $;
\item The distance between any pair of adjacent supports must be \textbf{no more than} $ d $. The distance between supports $ (i, j_1) $ and $ (i, j_2) $ is $ |j_1 - j_2| - 1 $.
\end{enumerate}
Building just one bridge is boring. Therefore, Rudolf decided to build $ k $ bridges on \textbf{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 \textbf{minimize} the total cost of installing supports.
\section{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 $.
\section{Output}
For each test case, output a single number — the minimum total cost of supports installation.
\end{document}题目大意：鲁道夫想帮助他的朋友贝尔纳德解决过河迟到的问题，因此他打算在河上建桥。河是一个有n行m列的网格，每个交叉点都有一个深度值。鲁道夫可以在一行的任意位置建桥，建桥的成本与该位置的深度有关。他需要在连续的k行上分别建桥，并希望最小化建桥的总成本。 输入数据格式：第一行包含一个整数t，表示测试用例的数量。每个测试用例的第一行包含四个整数n、m、k和d，分别表示网格的行数、列数、建桥的数量和支撑间的最大距离。接下来的n行，每行包含m个正整数，表示河的深度。 输出数据格式：对于每个测试用例，输出一个数字，表示安装支撑的最小总成本。 LaTeX格式： \documentclass{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{graphicx} \usepackage{hyperref} \usepackage{listings} \usepackage{xcolor} \title{E. Rudolf and k Bridges} \author{} \date{} \begin{document} \maketitle \section{Problem Statement} 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 \textbf{first} and \textbf{last} columns correspond to the river banks, so the depth for them is $ 0 $. \begin{center} \includegraphics[width=0.5\textwidth]{espresso} \end{center} 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: \begin{enumerate} \item A support must be installed in cell $ (i,1) $; \item A support must be installed in cell $ (i,m) $; \item The distance between any pair of adjacent supports must be \textbf{no more than} $ d $. The distance between supports $ (i, j_1) $ and $ (i, j_2) $ is $ |j_1 - j_2| - 1 $. \end{enumerate} Building just one bridge is boring. Therefore, Rudolf decided to build $ k $ bridges on \textbf{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 \textbf{minimize} the total cost of installing supports. \section{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 $. \section{Output} For each test case, output a single number — the minimum total cost of supports installation. \end{document}