← 返回题目列表

Codeforces · 2002/G

G. 晶格优化

中文机器翻译题面 查看原题

考虑一个具有 $$$n$$$ 行和 $$$n$$$ 列的网格图。令 $$$x$$$ 行和 $$$y$$$ 列中的单元格为 $$$(x,y)$$$。对于所有 $$$1\le x < n, 1\le y \le n$$$,存在从 $$$(x,y)$$$ 到 $$$(x+1,y)$$$ 的有向边,其值为非负整数 $$$d_{x,y}$$$,并且还存在从 $$$(x,y)$$$ 到 $$$(x,y+1)$$$ 的有向边,其值为非负整数$$$r_{x,y}$$$,对于所有$$$1\le x \le n,1\le y < n$$$。

最初,您位于 $$$(1,1)$$$,有一个空集 $$$S$$$。您需要沿着边缘行走并最终到达$$$(n,n)$$$。每当你传递一条边时,它的值就会被插入到$$$S$$$中。当您达到 $$$(n,n)$$$ 时,请最大化 $$$S$$$ 的 MEX$$$^{\text{∗}}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量$$$t$$$ ($$$1\le t\le100$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le20$$$) — 行数和列数。

接下来的 $$$n-1$$$ 行包含由单个空格分隔的 $$$n$$$ 整数 — 矩阵 $$$d$$$ ($$$0\le d_{x,y}\le 2n-2$$$)。

接下来的 $$$n$$$ 行包含由单个空格分隔的 $$$n-1$$$ 整数 — 矩阵 $$$r$$$ ($$$0\le r_{x,y}\le 2n-2$$$)。

保证所有$$$n^3$$$的总和不超过$$$8000$$$。

输出

对于每个测试用例,打印一个整数 - 当达到 $$$(n,n)$$$ 时 $$$S$$$ 的最大 MEX。

示例

输入 #1

2
3
1 0 2
0 1 3
2 1
0 3
3 0
3
1 2 0
0 1 2
2 0
1 2
0 1

输出 #1

3
2

输入 #2

1
10
16 7 3 15 9 17 1 15 9 0
4 3 1 12 13 10 10 14 6 12
3 1 3 9 5 16 0 12 7 12
11 4 8 7 13 7 15 13 9 2
2 3 9 9 4 12 17 7 10 15
10 6 15 17 13 6 15 9 4 9
13 3 3 14 1 2 10 10 12 16
8 2 9 13 18 7 1 6 2 6
15 12 2 6 0 0 13 3 7 17
7 3 17 17 10 15 12 14 15
4 3 3 17 3 13 11 16 6
16 17 7 7 12 5 2 4 10
18 9 9 3 5 9 1 16 7
1 0 4 2 10 10 12 2 1
4 14 15 16 15 5 8 4 18
7 18 10 11 2 0 14 8 18
2 17 6 0 9 6 13 5 11
5 15 7 11 6 3 17 14 5
1 3 16 16 13 1 0 13 11

输出 #2

14

注意

第一个测试用例中,网格图和其中一条最优路径如下:

在第二个测试用例中,网格图和最优路径之一如下: