P3458.第3题-数组的优美段
题目内容
给定一个长度为 n 的正整数数组 { a1,a2,…,an } ；
我们称一段连续子数组 al,al+1,...,ar ，为 优美段 ，当且仅当这段子数组的 gcd(al,al+1,...,ar)≤r−l+1 ;
请将整个数组划分成 k 段互不相交的优美段，覆盖原数组每个位置，求使 k 最大化，输出最大值 k 。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数 T(1≦T≦104) ，表示测试用例的组数；
除此之外，保证所有测试用例的 n 之和不超过 2×105 ；
随后对每组测试数据，按以下格式输入：
-
第一行输入一个整数 n(1≦n≦2×105) ;
-
第二行输入 n 个整数 a1,a2,...,an(1≦ai≦109)
输出描述
对于每组测试数据，新起一行输出一个整数，表示将数组划分为优美段的最大段数，如果没有任何分割方式输出 -1 。
样例1
输入
2
5
5 4 4 2 1
3
4 4 4
输出
3
-1
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
