本文主要是介绍蓝桥杯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;
}这篇关于蓝桥杯22年第十三届省赛-数组切分|线性DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
