A16246. Min-Sum-Max
编程题
普及/提高-
知识点
题目描述
The 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$ .
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$ .
输入格式
For each test case, output a single integer — the maximum number of subsegments among all possible ways to divide the array $a$ .
输出格式
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.
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.
输入输出样例
输入 #1
8 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 -5
输出 #1
2 1 3 2 1 6 5 3
说明/提示
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.
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.