CF2002G.Lattice Optimizing

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

考虑一个具有
$n$ 行和
$n$ 列的网格图。

对于所有 $x < n$ 的位置有一个权值 $d_{x,y}$

对于所有 $y < n$ 的位置有一个权值
$r_{x,y}$

从 $(1,1)$ 开始走，每次往下或往右走，最终到 $(n,n)$ 。

初始有一个空集合 $S$ 。若从 $(x,y)$ 走到 $(x+1,y)$ ，将 $d_{x,y}$ 加入 $S$ ；走到 $(x,y+1)$ 就加入 $r_{x,y}$ 。

需要最大化走到终点时的 $mex(S)$

其中， $mex(x)$ 定义为 $x$ 中最小未出现的 非负整数。

输入格式

第一行一个数 $T$ ，表示测试组数。

每组测试第一行一个整数 $n$ ，接下来 $n-1$ 行每行 $n$ 个数表示 $d$ 。

接下来 $n$ 行每行 $n-1$ 个数表示 $r$ 。

保证 $n$ 不超过 $20$ ，且所有 $n^3$ 的和不超过 $8000$ ，且 $d_{i,j}$ 和 $r_{i,j}$ 都不超过 $2n-2$ 。

输出格式

输出 $T$ 行表示每组测试数据的答案。

输入输出样例

输入#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

输入解题思路，AI测评打分。不知道怎么写?

首页