AdditionalFile5628.zip

#5628. 「POI2026 R2」Prognoza pogody

标签: 传统 | 时间限制: 3000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – II etap Dwukolorowe drzewo

Bajtek 刚刚开启了他的人工智能之旅。他决定将新学到的知识应用到天气预报问题上。其目标是输出一个由 $m$ 个整数组成的序列 $p_{1}, p_{2}, \ldots, p_{m}$，用于描述未来几天的气温预测。Bajtek 在一段时间前已经生成了这个序列，现在他想知道他的预测到底有多准。为此，他从网上下载了一个由 $n$ 个整数组成的序列 $t_{1}, t_{2}, \ldots, t_{n}$（其中 $m \leq n$），该序列记录了随后的实际气温。现在，他希望从实际气温序列中选择一个长度为 $m$ 的连续片段，使得该片段与预测序列的不匹配项数量尽可能少。由于初步实验的结果不尽如人意，Bajtek 可以先将他的预测序列进行循环移位，然后再与数据进行比较。

更正式地说，Bajtek 首先选择其预测序列的一个循环移位，即对于任意选定的 $1 \leq i \leq m$，得到序列 $p_{i}, p_{i+1}, \ldots, p_{m}, p_{1}, \ldots, p_{i-1}$。我们将移位后的预测序列记为 $p_{1}^{\prime}, p_{2}^{\prime}, \ldots, p_{m}^{\prime}$。接着，他将移位后的预测序列放置在数据序列中任意选定的起始位置 $j$ 上（其中 $1 \leq j \leq n-m+1$）。最后，他计算不匹配项的数量，即满足 $p_{k}^{\prime} \neq t_{j+k-1}$ 的位置 $k$ $(1 \leq k \leq m)$ 的数量。他希望通过这种方式使不匹配项的数量达到最小。请帮他计算出这个最小数量！

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ $(1 \leq m \leq n \leq 10000)$，分别表示数据序列的长度和预测序列的长度。第二行包含由 $n$ 个整数组成的实际数据序列 $t_{1}, t_{2}, \ldots, t_{n}$ $(-20 \leq t_{i} \leq 40)$。第三行包含由 $m$ 个整数组成的 Bajtek 生成的预测序列 $p_{1}, p_{2}, \ldots, p_{m}$ $(-20 \leq p_{i} \leq 40)$。

输出格式

输出一行一个整数，表示将预测序列的某种循环移位与数据比对时，可能产生的最小不匹配项数量。

样例

输入

5 3
-1 2 0 3 0
2 3 -1

输出

1

Bajtek 可以将预测序列循环移位，得到序列 $-1, 2, 3$，然后可以将其与从第一位开始的数据片段（即 $-1, 2, 0$）进行比对。此时它们仅在第三个位置不同，因此不匹配项的数量为 $1$。我们还可以看到，序列 $2, 3, -1$（$i=1$ 时的移位）、$3, -1, 2$（$i=2$ 时的移位）以及 $-1, 2, 3$（$i=3$ 时的移位）中没有任何一个与数据的连续片段完全相同，因此无法获得更小的不匹配项数量。

附加样例

1. $n=1000, m=500$，且对于 $1 \leq i \leq n$ 有 $t_{i}=(i \bmod 61)-20$，对于 $1 \leq i \leq m$ 有 $p_{i}=((i+13) \bmod 61)-20$。
2. $n=3000, m=2000$，且序列 $t$ 的前 $1500$ 个元素为 $0$，后 $1500$ 个为 $1$；序列 $p$ 的前 $1000$ 个元素为 $1$，后 $1000$ 个为 $0$。
3. $n=3500, m=2000$，且序列 $t$ 由七个长度均为 $500$ 的连续片段组成，其值依次为 $6, 5, 4, 3, 2, 1, 0$；而序列 $p$ 满足 $p_{i}=i \bmod 7$（对于 $1 \leq i \leq m$）。
4. $n=5000, m=3000$，且对于 $1 \leq i \leq n$ 有 $t_{i}=4$；而对于 $1 \leq i < m$ 有 $p_{i}=4$，且 $p_{m}=5$。
5. $n=10000, m=10000$，且对于 $1 \leq i \leq n$ 有 $t_{i}=i \bmod 3$；而对于 $1 \leq i \leq m$ 有 $p_{i}=i \bmod 4$。

数据范围与提示

详细子任务附加限制及分值如下表所示。