数组切分
代码实现
import java.io.*;
import java.util.*;
public class Main {
static final int N = 10010, M = (int) (Math.log10(N) / Math.log10(2)) + 3, mod = 1000000007;
static int[][] max = new int[N][M], min = new int[N][M];
static int[] f = new int[N], a = new int[N];
static int n;
public static void main(String[] args) {
FastReader sc = new FastReader();
n = sc.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
init();//初始化ST表
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = f[i - 1];//承接前面的结果
for (int j = 1; j < i; j++) {
if (check(j ,i))
//第i个数字产生的新序列
f[i] = (f[i] + f[j - 1]) % mod;
}
}
System.out.println(f[n]);
}
static boolean check(int l, int r) {//检查是否是连续的序列
int[] res = query(l, r);
return r - l == res[0] - res[1];
}
static int[] query(int l, int r) {
int[] res = new int[2];
int len = r - l + 1;
int k = (int)(Math.log10(len) / Math.log10(2));
res[0] = Math.max(max[l][k], max[r - (1 << k) + 1][k]);
res[1] = Math.min(min[l][k], min[r - (1 << k) + 1][k]);
return res;
}
static void init() {
for (int j = 0; j < M; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
if (j == 0) {
max[i][j] = a[i];
min[i][j] = a[i];
} else {
max[i][j] = Math.max(max[i][j - 1], max[i + (1 << j - 1)][j - 1]);
min[i][j] = Math.min(min[i][j - 1], min[i + (1 << j - 1)][j - 1]);
}
}
}
}
}
class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine(), " ");
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}