煎饼双端队列 - 题目

通常煎饼都是叠在一起供应的，但“无限煎饼屋”决定做出改变！这家餐厅的新广告噱头是从双端队列（deque）中供应煎饼。

你是餐厅的一名服务员，你的工作是供应双端队列中的每一个煎饼。顾客会一个接一个地到来，每人获得一个煎饼。你必须供应双端队列中最左侧或最右侧的煎饼；选择权在你手中。当一个煎饼被供应后，它会从双端队列中消失，露出它旁边的煎饼。或者，当只剩下一个煎饼时，你唯一的选择就是供应那一个，然后你的工作就完成了！

每个煎饼都有一个美味度。由于顾客无法选择他们得到的煎饼，因此每位顾客只有在他们得到的煎饼的美味度至少不低于之前所有顾客得到的煎饼的美味度时，才需要为他们的煎饼付费。（第一位顾客总是需要为他们的煎饼付费，因为在这种情况下没有之前的顾客。）

如果你以一种能使付费顾客人数最大化的顺序供应煎饼，那么会有多少位顾客为他们的煎饼付费？

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例由两行组成。第一行包含一个整数 $N$，表示双端队列中煎饼的数量。第二行包含 $N$ 个整数 $D_1, D_2, \dots, D_N$，其中 $D_i$ 表示双端队列中从左往右第 $i$ 个煎饼的美味度。

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是如果你以最大化付费人数的顺序供应煎饼，为煎饼付费的顾客人数。

$1 \le T \le 100$。 $1 \le D_i \le 10^6$，对于所有 $i$。

$2 \le N \le 20$。

$2 \le N \le 100$。

$2 \le N \le 10^5$。

4
2
1 5
4
1 4 2 3
5
10 10 10 10 10
4
7 1 3 1000000

Case #1: 2
Case #2: 3
Case #3: 5
Case #4: 2

在样例 1 中，有两种可能的供应顺序。如果你先供应美味度为 5 的煎饼，则只有那一个会被付费。如果你先供应美味度为 1 的煎饼，则两个都会被付费。

样例 2 是题目描述中的图片示例。以下是煎饼可以被供应的可能顺序（按美味度排列）。下划线的煎饼表示顾客会为其付费。

如你所见，有些顺序中有 3 个煎饼被付费，但没有一种顺序能让全部 4 个都被付费。

在样例 3 中，无论供应顺序如何，所有煎饼都会被付费。

在样例 4 中，无论你先供应哪个煎饼，中间的两个永远不会被付费。你能做的最好情况是在美味度为 1000000 的煎饼之前供应美味度为 7 的煎饼。

QOJ.ac