蓝桥杯22年第十三届省赛-数组切分|线性DP

题目链接：

蓝桥杯2022年第十三届省赛真题-数组切分 - C语言网 (dotcpp.com)

 1.数组切分 - 蓝桥云课 (lanqiao.cn)

这道题C语言网数据会强一些。 

 说明：

对于一个切分的子数组，由于数组是1-N的一个排列，所以每个数唯一 可以用子数组最大值-最小值==子数组长度-1（子数组右端点索引 -左端点索引+1-1）来判断 。
  
 尝试题目求什么，我们就设dp数组为 什么，那么设f[i]为 前i个数能有f[i]种方案， 
 观察样例，手工计算， A=1，3，2，4 
 i为1时，方案为 ： 
 {1} 
 i为2时，方案为： 
  {1}{3}    而{1，3}不行   
 i为3时，方案为 ：
 {1}{3}{2}，{1}{3，2}，{1，3，2} 而{1，3}{2}不行   
 i为4时，方案为：
  {1}{3}{2}{4}，{1}{3，2}{4}，{1，3，2}{4} ，{1}{3，2，4}，{1，3，2，4} 
  而{1}{3}{2，4}，{1，3}{2}{4}不行 
  
  发现当加入第i个数是时，如果把第j个数和第i个数划成一组，如果这个划分合法，
  那么他就能和f[j-1] 的每个方案 组合成 合法方案，于是累加上[j，i]划分合法时每个
  f[j-1]就是f[i]的值 。

 注意：如果1到i所有数在一个切分里能组成合法的区间，这时的j-1为0 ,故初始化f[0]=1

在c语言网用scanf输入，才能ac，用cin有一个测试点过不了。

代码：

#include 
//#define int long long
using namespace std;
const int N=1e5+10;
 /*
 对于一个切分的子数组，由于数组是1-N的一个排列，所以每个数唯一
 可以用子数组最大值-最小值==子数组长度-1（子数组右端点索引
 -左端点索引+1-1）来判断 
  
 尝试题目求什么，我们就设dp数组为 什么，那么设f[i]为 前i个数能有
 f[i]种方案， 
 观察样例，手工计算， A=1，3，2，4 
 i为1时，方案为 ： 
 {1} 
  i为2时，方案为： 
  {1}{3}    而{1，3}不行   
 i为3时，方案为 ：
 {1}{3}{2}，{1}{3，2}，{1，3，2} 而{1，3}{2}不行   
 i为4时，方案为：
  {1}{3}{2}{4}，{1}{3，2}{4}，{1，3，2}{4} ，{1}{3，2，4}，{1，3，2，4} 
  而{1}{3}{2，4}，{1，3}{2}{4}不行 
  
  发现当加入第i个数是时，如果把第j个数和第i个数划成一组，如果这个划分合法，
  那么他就能和f[j-1] 的每个方案 组合成 合法方案，于是累加上[j，i]划分合法时每个
  f[j-1]就是f[i]的值 。
  注意：如果1到i所有数在一个切分里能组成合法的区间，这时的j-1为0 ,故初始化f[0]=1
 */
 
 
int a[N]; 
//表示前i个数能有f[i]种切分方法 
int f[N]; 
int mod=1000000007;
int n;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++){
	//	cin>>a[i];
  //开long long 之后 用scanf格式控制符要用lld
  //用scanf要关掉上面的ios语句 
		scanf("%d",&a[i]); 
	}
	
 
  //需要初始化0处为1，因为如果1到i所有数在一个切分里能组成合法的区间
	//这时的j-1为0 ,故f[0]=1
  f[0]=1;
	f[1]=1;
	for(int i=2;i<=n;i++){
		//序列最小值减最大值等于序列长度-1，即为自然数 
		int ma=a[i],mi=a[i];
	for(int j=i;j>=1;j--){
		//维护最值 
		ma=max(ma,a[j]),mi=min(mi,a[j]);
		if(ma-mi==i-j){
			f[i]=(f[i]+f[j-1])%mod;
		}
	}
	
	}
	
	cout<
   return 0;
}