「DROI」Round 1 失控

Luogu

IDLGP8983

Time800ms

Memory128MB

DifficultyP6

动态规划 DP洛谷原创O2优化动态规划优化

给定一个 $n \times m$ 的矩阵 $G$ 和两个长度为 $m$ 的排列 $p,q$。我们称元素 $G_{i,j}$ 是**失控的**，当且仅当 $\vert G_{i,j} - G_{i-1,p_j} \vert > C$ **且** $\vert G_{i,j} - G_{i+1,q_j} \vert > C$，其中 $C$ 是给定的常数。特殊地，我们规定无论如何第 $1$ 行和第 $n$ 行的元素都不是失控的。此时再给定两个长度为 $k$ 的序列 $A$ 和 $B$。你将有 $k$ 种操作：其中第 $i$ 种操作是将某一行所有元素增加 $A_i$，这将会花费 $B_i$ 的代价。**每种操作可以使用的次数不限，但对于每一行，你只可以进行这些操作中的一种或不操作。并且，你必须保证任意相邻两行最多有一行进行操作。** 请问要使得矩阵 $G$ 中所有元素均不失控，至少要花费的代价是多少（数据保证有解）？ ## Input 第一行四个整数，分别为 $n,m,k,C$。接下来 $n+4$ 行，前 $n$ 行每行 $m$ 个数，表示矩阵 $G$，第 $n+1$ 和 $n+2$ 行每行 $m$ 个数，分别表示排列 $p$ 和 $q$，最后两行每行 $k$ 个数，分别表示序列 $A$ 和 $B$。 ## Output 输出一行一个整数，表示答案。 [samples] ## Background 失控的，或许反而是理智的。 ## Note #### 样例解释 #1 显然对于样例一，不用进行任何操作就能保证所有元素均不失控。 ------------ #### 样例解释 #2 对第三行使用 $3$ 操作，对第七行使用 $4$ 操作即可。可以证明不存在更优的方案。 ------------ #### 数据范围 **「本题采用捆绑测试」** - $\operatorname{Subtask} 1(10\%)$：$n,m,k \leq 8$。 - $\operatorname{Subtask} 2(30\%)$：$m\leq 50,k\leq 100$。 - $\operatorname{Subtask} 3(20\%)$：$m\leq 50,k\leq 1000$。 - $\operatorname{Subtask} 4(40\%)$：无特殊限制。对于 $100\%$ 的数据满足：$3 \leq n\leq 50$，$1 \leq m \leq 300$，$0 \leq k \leq 2000$，$C,G_{i,j},A_i,B_i \leq 10^6$。 **本题输入量较大，请用较快的输入方法。** ------------ #### 提示 - 本题不卡常，如果你认为自己的算法差一点就能跑过下一个 Subtask 却没有跑过，那么请不要纠结于无意义的卡常，因为差的这一点可能需要更优秀的算法来弥补。

Samples

Input #1

3 3 5 10
1 2 6
7 3 11
9 44 5
2 3 1
1 3 2
5 10 15 20 25
6 6 6 6 6

Output #1

Input #2

8 8 8 28
49 11 44 31 25 37 41 1 
29 38 46 21 21 17 45 47 
1 37 11 31 8 15 15 47 
21 47 15 6 11 9 40 28 
21 29 1 11 39 15 21 35 
26 20 3 38 1 41 27 21 
41 41 31 16 11 1 24 3 
33 15 23 26 7 47 49 8 
3 8 2 4 6 5 1 7 
7 5 8 3 6 1 4 2 
36 13 12 3 38 49 22 55 
20 24 2 30 26 25 17 25

Output #2

API Response (JSON)

{
  "problem": {
    "name": "「DROI」Round 1 失控",
    "description": {
      "content": "给定一个 $n \\times m$ 的矩阵 $G$ 和两个长度为 $m$ 的排列 $p,q$。 我们称元素 $G_{i,j}$ 是**失控的**，当且仅当 $\\vert G_{i,j} - G_{i-1,p_j} \\vert > C$ **且** $\\vert G_{i,j} - G_{i+1,q_j} \\vert > C$，其中 $C$ 是给定的常数。特殊地，我们规定无论如何第 $1$ 行和第",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 800,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8983"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个 $n \\times m$ 的矩阵 $G$ 和两个长度为 $m$ 的排列 $p,q$。\n\n我们称元素 $G_{i,j}$ 是**失控的**，当且仅当 $\\vert G_{i,j} - G_{i-1,p_j} \\vert > C$ **且** $\\vert G_{i,j} - G_{i+1,q_j} \\vert > C$，其中 $C$ 是给定的常数。特殊地，我们规定无论如何第 $1$ 行和第...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments