蓝桥杯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 <bits/stdc++.h>
//#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]=1f[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<<f[n];return 0;
}