ez problem 2

luogu_gza · 2026-07-17 10:22:16 · 学习·文化课

题面（imo2022p6）

令 n 为一个正整数，一个「北欧方阵」是一个包含 1 至 n^2 所有整数的 n \times n 的方格表，使得每个方格中恰有一个数字，两个相异方格是相邻的如果它们有公共边，一个方格被称为「山谷」，若其内的数字比所有相邻方格内的数字都小，一条「上坡路径」是一个包含一或多个方格的序列，满足：（1）序列的第一个方格是山谷；（2）序列中随后的每个方格都和前一个方格相邻；（3）序列中方格所写的数字递增，求一个北欧方阵中上坡路径数量的最小可能值，以 n 的函数表示之.

::::info[题解] 我们先考虑对于一个方阵怎么算上坡路径数量，不难设计 dp。

令 f_{i,j} 表示 (i,j) 结尾的路径个数，对于山谷有 f_{i,j}=1，对于非山谷就是它四周的 f 值加起来。

上坡路径数量就是 \sum_{1 \leq i,j \leq n} f_{i,j}。

这本质上是一个 dag 路径计数，为了最小化上坡路径数量我们肯定希望每条边对答案的贡献最少，自然而然的，我们会希望每条边的贡献都是 1。山谷的 f 值是凭空产生的，因此我们也希望山谷个数尽可能少，也就是只有一个山谷。

因此可以有 \sum_{1 \leq i,j \leq n}f_{i,j} \geq 1+2n(n-1)（1 是因为山谷，2n(n-1) 是因为总共有 2n(n-1) 条边）。

稍微构造一下 n=2,n=3 的情形发现这是可以做到的，这里给一下构造。

1 2
4 3

1 2 3
4 8 5
9 7 6

这提示我们可以把点分为两类，一类为终止点，一类为非终止点，非终止点成一棵树，终止点互不相邻。构造的时候只需要让非终止点按照 dfs 序编号，终止点把剩下的数填进去就行了，显然满足了 \sum_{1 \leq i,j \leq n}f_{i,j} \geq 1+2n(n-1) 的取等条件。