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

· · 题解

题目大意

给定一个 1 \sim N 的一个排列，要求你把其切分为若干个子数组，每个子数组中的整数都恰好可以组成一段连续的自然数。

你需要回答具体有多少种切分原序列的方案，并将其对于 10^{9} +7 取模。

具体思路

这是一道明显的 dp 问题。我们可以想到状态定义，f_{i} 表示前 i 个数的方案数总和。如果有一个区间 \left [ j,i \right ] 是可以被切分出来的，那么 f_{i}=f_{i}+f_{j-1}。可以理解为，对于 f_{i} 中需要切分出来 \left [ j,i \right ] 的方案数，其实就是切分前 j-1 个数的方案数，也就是 f_{j-1}。

那么，如何判断这个数组是否可以切分出来呢？

题目给出的数组是 1 \sim n 的一个排列，也就是其中没有重复的元素。所以，我们可以得出，对于区间 \left [ l,r \right ]，当 r-l 为序列的极差（最大值与最小值的差）时，这个序列就可以被切分出来。

那么代码就很好写了（记得取模）。

代码实现

#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;
}