310675: CF1868E. Min-Sum-Max
Description
Tom is waiting for his results of Zhongkao examination. To ease the tense atmosphere, his friend, Daniel, decided to play a game with him. This game is called "Divide the Array".
The game is about the array $a$ consisting of $n$ integers. Denote $[l,r]$ as the subsegment consisting of integers $a_l,a_{l+1},\ldots,a_r$.
Tom will divide the array into contiguous subsegments $[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$, such that each integer is in exactly one subsegment. More formally:
- For all $1\le i\le m$, $1\le l_i\le r_i\le n$;
- $l_1=1$, $r_m=n$;
- For all $1< i\le m$, $l_i=r_{i-1}+1$.
Denote $s_{i}=\sum_{k=l_i}^{r_i} a_k$, that is, $s_i$ is the sum of integers in the $i$-th subsegment. For all $1\le i\le j\le m$, the following condition must hold:
$$ \min_{i\le k\le j} s_k \le \sum_{k=i}^j s_k \le \max_{i\le k\le j} s_k. $$
Tom believes that the more subsegments the array $a$ is divided into, the better results he will get. So he asks Daniel to find the maximum number of subsegments among all possible ways to divide the array $a$. You have to help him find it.
InputThe first line of input contains a single integer $t$ ($1\le t\le 50$) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $n$ ($1\le n\le 300$) — the length of the array $a$.
The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9\le a_i\le 10^9$) — the elements of the array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.
OutputFor each test case, output a single integer — the maximum number of subsegments among all possible ways to divide the array $a$.
ExampleInput8 3 -1 5 4 2 2023 2043 6 1 4 7 -1 5 -4 5 -4 0 3 -18 10 1 998244853 10 -4 2 5 -10 4 8 2 9 -15 7 7 -7 3 8 -9 -2 2 4 4 -5 5 -2 -5Output
2 1 3 2 1 6 5 3Note
In the first test case, Daniel can divide the array into $[-1]$ and $[5,4]$, and $s=[-1,9]$. It can be shown that for any $i=j$, the condition in the statement is already satisfied, and for $i=1,j=2$, we have $\min(-1,9)\le (-1)+9\le \max(-1,9)$.
In the second test case, if Daniel divides the array into $[2023]$ and $[2043]$, then for $i=1,j=2$ we have $2023+2043>\max(2023,2043)$, so the maximum number of subsegments is $1$.
In the third test case, the optimal way to divide the array is $[1,4,7],[-1],[5,-4]$.
In the fourth test case, the optimal to divide the array way is $[-4,0,3,-18],[10]$.
In the fifth test case, Daniel can only get one subsegment.
Output
这个题目是关于将一个由n个整数组成的数组a划分为若干个连续的子段的问题。要求每个整数恰好位于一个子段中。子段的总和满足一个特定的条件,即对于任意1≤i≤j≤m,都有以下条件成立:
\[\min_{i\le k\le j} s_k \le \sum_{k=i}^j s_k \le \max_{i\le k\le j} s_k\]
其中,\(s_k\)是第k个子段中整数的和。汤姆认为,数组a被划分的子段越多,他得到的中考结果就越好。因此,他要求丹尼尔找到所有可能的划分方式中子段的最大数量。
输入输出数据格式:
输入:
- 第一行包含一个整数t(1≤t≤50),表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n(1≤n≤300),表示数组a的长度。
- 每个测试用例的第二行包含n个整数\(a_1, a_2, \ldots, a_n\)(-10^9≤ai≤10^9),表示数组a的元素。
- 保证所有测试用例的n之和不超过1000。
输出:
- 对于每个测试用例,输出一个整数,表示所有可能的划分方式中子段的最大数量。题目大意: 这个题目是关于将一个由n个整数组成的数组a划分为若干个连续的子段的问题。要求每个整数恰好位于一个子段中。子段的总和满足一个特定的条件,即对于任意1≤i≤j≤m,都有以下条件成立: \[\min_{i\le k\le j} s_k \le \sum_{k=i}^j s_k \le \max_{i\le k\le j} s_k\] 其中,\(s_k\)是第k个子段中整数的和。汤姆认为,数组a被划分的子段越多,他得到的中考结果就越好。因此,他要求丹尼尔找到所有可能的划分方式中子段的最大数量。 输入输出数据格式: 输入: - 第一行包含一个整数t(1≤t≤50),表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n(1≤n≤300),表示数组a的长度。 - 每个测试用例的第二行包含n个整数\(a_1, a_2, \ldots, a_n\)(-10^9≤ai≤10^9),表示数组a的元素。 - 保证所有测试用例的n之和不超过1000。 输出: - 对于每个测试用例,输出一个整数,表示所有可能的划分方式中子段的最大数量。