A16662 | $Circle of Apple Trees$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

有 $n$ 棵苹果树围成一个圆圈。每棵树上都有一个苹果，第 $i$ 棵树上的苹果美丽值为 $b_i$，其中 $1 \le i \le n$。你开始站在第 1 棵树前。 在每棵树前，你可以选择吃掉该树上的苹果，或者跳过不吃。每做出选择后，你会移动到下一棵树：从第 $i$ 棵树前往第 $i+1$ 棵树（$1 \le i \le n-1$），从第 $n$ 棵树则回到第 1 棵树。你会这样不断循环地经过这些树。 但你有一个特别的限制：只有当当前苹果的美丽值严格大于你上一次吃掉的苹果的美丽值时，你才能吃下去。例如，若 $b = [2, 1, 2, 3]$，你若在第 1 棵树吃了苹果（美丽值 $2$），则不能吃第 2、3 棵树的苹果，因为它们的美丽值都不大于 $2$。但你可以在第 4 棵树吃下苹果，因为 $b_4 = 3 > 2$。 注意，每遇到一个苹果时你都可以选择先跳过不吃，之后某轮循环再次遇到时再选择是否吃掉。 你的任务是，若你每一步都做出最优决策，最多能吃到多少个苹果。

每组测试包含多个测试用例。第一行包含整数 $t$（$1 \le t \le 500$），表示测试用例数。 每组测试用例第一行包含一个整数 $n$（$1 \le n \le 100$），表示苹果树数量。 第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \le b_i \le n$），表示每棵树上的苹果美丽值。 注意，所有测试用例中 $n$ 的总和没有额外限制。

对每个测试用例，输出一个整数，表示你最多可以吃到的苹果数量。

输入 #1

3
4
2 2 2 2
5
1 4 5 1 2
6
5 4 2 1 2 3

输出 #1

1
4
5

C++ 编辑器

输入

输出