专栏文章

题解：P13934 [蓝桥杯 2022 省 Java B] 数组切分

CCade_Cunningham
P13934题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio08twz
此快照首次捕获于
2025/12/02 11:14
3 个月前
此快照最后确认于
2025/12/02 11:14
3 个月前
查看原文

题目大意

给定一个 1∼N1 \sim N 的一个排列，要求你把其切分为若干个子数组，每个子数组中的整数都恰好可以组成一段连续的自然数。
你需要回答具体有多少种切分原序列的方案，并将其对于 109+710^{9} +7 取模。

具体思路

这是一道明显的 dp 问题。我们可以想到状态定义，fif_{i} 表示前 ii 个数的方案数总和。如果有一个区间 [j,i]\left [ j,i \right ] 是可以被切分出来的，那么 fi=fi+fj−1f_{i}=f_{i}+f_{j-1}。可以理解为，对于 fif_{i} 中需要切分出来 [j,i]\left [ j,i \right ] 的方案数，其实就是切分前 j−1j-1 个数的方案数，也就是 fj−1f_{j-1}。
那么，如何判断这个数组是否可以切分出来呢？
题目给出的数组是 1∼n1 \sim n 的一个排列，也就是其中没有重复的元素。所以，我们可以得出，对于区间 [l,r]\left [ l,r \right ]，当 r−lr-l 为序列的极差（最大值与最小值的差）时，这个序列就可以被切分出来。
那么代码就很好写了（记得取模）。

代码实现

CPP
#include<bits/stdc++.h>
using namespace std;
int n,a[10010],f[10010];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[0]=1;//初始化 
    for(int i=1;i<=n;i++)
    {
    	int minn=2100000000;//min 初始化 
    	int maxx=-2100000000;//max 初始化 
    	for(int j=i;j>=1;j--)
		//由于状态定义是对于区间 [j,i] 的，
		//所以从 i 开始倒序枚举。 
    	{
    		minn=min(minn,a[j]);//记录 
    		maxx=max(maxx,a[j]);
    		if(maxx-minn==i-j) f[i]=(f[i]+f[j-1])%1000000007;
			//判断转移的条件，取模 
		}
	}
	cout<<f[n];//答案 
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...