CF2207C Where's My Water?
题目描述
[Level 3 — David Luis Ortega, Where's My Water? ](https://www.youtube.com/watch?v=3yV8PPnShSw) 设 $n,h$ 为正整数。Swampy 鳄鱼需要给他的浴缸注水，你的任务是帮他引来水。Swampy 的家上方有一个 $h \times n$ 的网格，由泥土和水瓷砖组成，$n$ 列编号为 $1, \ldots, n$。在第 $i$ 列的最底部，有 $a_i$ 个瓷砖是泥土，剩下的顶端都是水瓷砖。
为了把水送到 Swampy，你可以在任意不是泥土的瓷砖上安装排水口。安装排水口后，所有能够通过仅向下、向左或向右移动且不经过泥土瓷砖而到达排水口的水瓷砖都会被引走。
例如，在下图中，将排水口放在符号 $\times$ 所在的位置，除了最左上方和最右上方的水瓷砖之外，其他瓷砖都能够被排走，总共可以引走 $10$ 个瓷砖的水：
请问在最多放置两个排水口的情况下，最多能够获取多少水瓷砖？注意，如果某个水瓷砖能够被两个排水口同时引走，只计一次。
输入格式
每个测试点包含多个测试用例。第一行包含整数 $t$（$1 \le t \le 10^3$），表示测试用例的组数。
每个测试用例的第一行包含两个整数 $n$ 和 $h$（$1 \leq n \leq 2000, 1 \leq h \leq 10^9$），分别表示网格的列数和高度。
接下来一行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq h$），表示第 $i$ 列泥土的高度。
保证所有测试用例中 $n$ 的总和不超过 $2000$。
输出格式
对于每个测试用例，输出一个整数，表示在最多放置两个排水口的情况下能够获取的最大水瓷砖数。
说明/提示
在第一个测试用例中，网格如题面所示。可以如图所示放置排水口，共能引走 $14$ 块水瓷砖：
在第二个测试用例中，网格如下：
可以如下图所示放置排水口，引走所有 $43$ 块水瓷砖：
在第三个测试用例中，整个网格只有一个泥土瓷砖，无法安装排水口，因此答案为 $0$。
由 ChatGPT 5 翻译