Minimize the Thickness

题意翻译

## 题目描述 给你一个长度为 $n$ 的数组 $a$，第 $i$ 个元素为 $a_i$。我们可以将 $a$ 分为若干个连续的不为空的子段，但前提条件是每个元素都要在一个子段里，且每个子段里的元素和都必须相等。 例如，我们有一个长度为 $6$ 的数组 $[55,45,30,30,40,100]$，如果我们把这个数组分为 $[55,45]$、$[30,30,40]$ 和 $[100]$ 三个子段的话，那么每个子段里的元素和都为 $100$。 定义若干个子段的厚度为这些子段里元素最多的子段里的元素个数，你的目标就是给定一个长度为 $n$ 的数组，找到一种分割子段的方法，使得分割后所有子段的厚度最小。 ## 输入格式 第一行，一个正整数 $t(1 \leq t \leq 100)$，表示数据组数。 每组输入由两行组成： 第一行是一个正整数 $n(1 \leq n \leq 2000)$，表示数组的长度。 第二行，$n$ 个正整数，表示你需要分割的数组。 数据保证 $\sum n \leq 2000$。 ## 输出格式 对于每一组数据，输出一个正整数，表示可以得到的最小厚度。 （Translated by @[owo_ImposterAnYu_owo](https://www.luogu.com.cn/user/510555)）

题目描述

You are given a sequence $ a=[a_1,a_2,\dots,a_n] $ consisting of $ n $ positive integers. Let's call a group of consecutive elements a segment. Each segment is characterized by two indices: the index of its left end and the index of its right end. Denote by $ a[l,r] $ a segment of the sequence $ a $ with the left end in $ l $ and the right end in $ r $ , i.e. $ a[l,r]=[a_l, a_{l+1}, \dots, a_r] $ . For example, if $ a=[31,4,15,92,6,5] $ , then $ a[2,5]=[4,15,92,6] $ , $ a[5,5]=[6] $ , $ a[1,6]=[31,4,15,92,6,5] $ are segments. We split the given sequence $ a $ into segments so that: - each element is in exactly one segment; - the sums of elements for all segments are equal. For example, if $ a $ = \[ $ 55,45,30,30,40,100 $ \], then such a sequence can be split into three segments: $ a[1,2]=[55,45] $ , $ a[3,5]=[30, 30, 40] $ , $ a[6,6]=[100] $ . Each element belongs to exactly segment, the sum of the elements of each segment is $ 100 $ . Let's define thickness of split as the length of the longest segment. For example, the thickness of the split from the example above is $ 3 $ . Find the minimum thickness among all possible splits of the given sequence of $ a $ into segments in the required way.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Each test case is described by two lines. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2000 $ ) — the length of the sequence $ a $ . The second line of each test case contains exactly $ n $ integers: $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^6 $ ) — elements of the sequence $ a $ . It is guaranteed that the sum of $ n $ for all test cases does not exceed $ 2000 $ .

输出格式

For each test case, output one integer — the minimum possible thickness of a split of the sequence $ a $ into segments. Note that there always exist a split, you can always consider whole sequence as one segment.

输入输出样例

输入样例 #1

4
6
55 45 30 30 40 100
4
10 23 7 13
5
10 55 35 30 65
6
4 1 1 1 1 4

输出样例 #1

3
4
2
3

说明

The split in the first test case is explained in the statement, it can be shown that it is optimal. In the second test case, it is possible to split into segments only by leaving a single segment. Then the thickness of this split is equal to the length of the entire sequence, that is, $ 4 $ . In the third test case, the optimal split will be $ [10, 55], [35, 30], [65] $ . The thickness of the split equals to $ 2 $ . In the fourth test case possible splits are: - $ [4] + [1, 1, 1, 1] + [4] $ ; - $ [4, 1, 1] + [1, 1, 4] $ .

题目大意：给定一个数组，要求将其分割成若干个连续的子段，使得每个子段的元素和相等，求分割后所有子段中元素最多的子段的最小元素个数。

输入格式：第一行一个正整数t，表示数据组数。每组数据第一行一个正整数n，表示数组长度。第二行n个正整数，表示数组中的每个元素。

输出格式：对于每组数据，输出一个正整数，表示可以得到的最小厚度。题目大意：给定一个数组，要求将其分割成若干个连续的子段，使得每个子段的元素和相等，求分割后所有子段中元素最多的子段的最小元素个数。 输入格式：第一行一个正整数t，表示数据组数。每组数据第一行一个正整数n，表示数组长度。第二行n个正整数，表示数组中的每个元素。 输出格式：对于每组数据，输出一个正整数，表示可以得到的最小厚度。