lanqiaoOJ 2148 数组切分

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
const int N = 10010 ,M = 1e9+7;
typedef long long LL ;
LL dp[N] ;//\\表示前i个数可以划分的自然数组的数量
LL a[N] ;//\\存储原数组
int main(){
  int n ; cin >> n ;
  for(int i = 1 ;i <= n ; i ++) cin >>a[i] ;
  dp[0] = 1 ;//\\初始化
  for(int i = 1; i <= n ; i ++){
    LL mi,ma ;//\\定义一个最大值和最小值
    mi = ma = a[i];\\当最大值减最小值等于数组长度时说明可以组成一个自然数组
    for(int j = i ; j >= 1 ; j --){
      mi = min(mi,a[j]) ; ma = max(ma,a[j]) ;
      if(i-j==ma-mi){//\\j--i 可以组成一个自然数组，然后j-1 之前的数组成的自然数组都可以组成i的自然数组
        dp[i] = (dp[i] + dp[j-1]) % M ;
      }
    }
  }
  cout << dp[n] << endl ;
  return 0 ;
}