$区间最大值-区间最小值 == 区间长度 <=> 这段区间数值连续$
这个怎么来的请看 $y$总 视频,连续区间数的讲解
$f_i$ 表示以前 $i$ 个元素分组的所有方案, 然后通过枚举以最后一组的所在的区间划分。
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, MOD = 1e9 + 7;
int n;
int a[N];
int f[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
f[0] = 1;
for (int i = 1; i <= n; i ++ )
{
int Min = n + 1, Max = 0;
for (int j = i; j; j -- )
{
Min = min(Min, a[j]), Max = max(Max, a[j]);
if (i - j + 1 == Max - Min + 1)
f[i] = (f[i] + f[j - 1]) % MOD;
// 最后一组区间是 [j, i] 有多少方案, 取决于前 j - 1 个元素有多少划分方案
}
}
cout << f[n] << endl;
return 0;
}