时间复杂度O(n^2)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10010, mod = 1000000007;
int n;
int a[N];
int f[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
f[0] = 1;
for(int i = 1; i <= n; i ++)
{
int Min = a[i], Max = a[i];
for(int j = i; j > 0; j --)
{
Min = min(Min, a[j]), Max = max(Max, a[j]);
if(i - j == Max - Min)
f[i] = (f[i] + f[j - 1]) % mod;
}
}
printf("%d\n", f[n]);
}
6
油石粒
为什么j一定要倒序遍历呀
这里 f[i] 分类的依据是最后一段是哪段,假设是j ~ i这段,那么j ~ i要满足题意,就需要j ~ i这一段的最大值 - 最小值 == 区间长度, 如果我们的 j 从 i 倒叙开始枚举,是可以正确统计出 j ~ i中的最大值和最小值,如果正序枚举j的话,那我们得到的最大值和最小值是(1 ~ j)的最值而不是j ~ i的最值,就不正确了。
明白了,谢谢!