第十三届蓝桥杯JavaB组省赛G题——数组切分 (AC)

阳光穿透心脏的1/2处 2023-09-28 23:12 20阅读 0赞

[CSDN话题挑战赛第2期][CSDN_2]  
参赛话题：[算法题解][Link 1]

#### 目录 ####

*  1.数组切分
 *   *  1.问题描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
     *  7.原题连接
 *  2.解题思路
 *  模板代码

## 1.数组切分 ##

### 1.问题描述 ###

已知一个长度为  N N N 的数组:  A 1 , A 2 , A 3 , … A N A\_\{1\}, A\_\{2\}, A\_\{3\}, \\ldots A\_\{N\} A1,A2,A3,…AN 恰好是  1 ∼ N 1 \\sim N 1∼N 的一个排列。现在要求你将  A A A 数组切分成若干个 (最少一个, 最多  N N N 个) 连续的子数组, 并且 每个子数组中包含的整数恰好可以组成一段连续的自然数。

例如对于  A = 1 , 3 , 2 , 4 A=\{1,3,2,4\} A=1,3,2,4, 一共有 5 种切分方法:

1324 \{1\}\{3\} \{2\}\{4\} 1324 : 每个单独的数显然是 (长度为 1 的) 一段连续的自然数。

\{ 1 \} \{ 3 , 2 \} \{ 4 \} : \{ 3 , 2 \} \\\{1\\\}\\\{3,2\\\} \\\{4\\\}:\\\{3,2\\\} \{ 1\}\{ 3,2\}\{ 4\}:\{ 3,2\} 包含  2 2 2 到  3 3 3 , 是 一段连续的自然数, 另外  1 \{1\} 1 和  4 \{4\} 4 显然 也是。

\{ 1 \} \{ 3 , 2 , 4 \} : \{ 3 , 2 , 4 \} \\\{1\\\}\\\{3,2,4\\\}:\\\{3,2,4\\\} \{ 1\}\{ 3,2,4\}:\{ 3,2,4\} 包含  2 2 2 到  4 4 4 , 是一段连续的自然数, 另外  1 \{1\} 1 显然也是。

\{ 1 , 3 , 2 \} \{ 4 \} : \{ 1 , 3 , 2 \} \\\{1,3,2\\\} \\\{4\\\}:\\\{1,3,2\\\} \{ 1,3,2\}\{ 4\}:\{ 1,3,2\} 包含  1 1 1 到  3 3 3 , 是 一段连续的自然数, 另外  4 \{4\} 4 显然也是。

\{ 1 , 3 , 2 , 4 \} \\\{1,3,2,4\\\} \{ 1,3,2,4\} : 只有一个子数组, 包含  1 1 1 到  4 4 4 , 是 一段连续的自然数。

### 2.输入格式 ###

第一行包含一个整数  N N N 。第二行包含  N N N 个整数, 代表  A A A 数组。

### 3.输出格式 ###

输出一个整数表示答案。由于答案可能很大, 所以输出其对 `1000000007` 取模后的值

### 4.样例输入 ###

4  
1 3 2 4

### 5.样例输出 ###

### 6.数据范围 ###

对于  30 % 30 \\% 30% 评测用例,  1 ≤ N ≤ 20 1 \\leq N \\leq 20 1≤N≤20.

对于  100 % 100 \\% 100% 评测用例,  1 ≤ N ≤ 10000 1 \\leq N \\leq 10000 1≤N≤10000.

### 7.原题连接 ###

[数组切分][Link 2]

## 2.解题思路 ##

一道比较明显的`dp`题，首先考虑一段子数组在包含一段连续的自然数时，会有什么性质？设区间 \[ L , R \] \[L,R\] \[L,R\]的值域为 \[ m i n , m a x \] \[min,max\] \[min,max\]，不难发现如果该区间是一段连续自然数时，将会满足:  
 m a x − m i n = R − L max-min=R-L max−min=R−L  
也就是区间的最大值减去最小值等于右端下标减去左端下标。有了这个性质以后，从数据范围考虑， n n n 最多为 `1e4` ，说明我们可以进行一个  n 2 n^2 n2 的  d p dp dp 转移。  
设  f \[ i \] f\[i\] f\[i\] 为只考虑前  i i i 个数能切分的情况数。当区间 \[ j , i \] \[j,i\] \[j,i\]是一段连续自然数时，我们可以进行状态转移 f \[ i \] = ( f \[ i \] + f \[ j − 1 \] ) f\[i\]=(f\[i\]+f\[j-1\]) f\[i\]=(f\[i\]\+f\[j−1\])  
对于每个  i i i 我们可以从倒着遍历回去一直到下标  1 1 1 ，同时开两个变量维护已遍历的数中的最大值和最小值，当此时区间是一段连续自然数时我们可以进行一次转移。  
初始化时应该置  f \[ 0 \] = 1 f\[0\]=1 f\[0\]=1。  
整体时间复杂度： O ( n 2 ) O(n^2) O(n2)

## 模板代码 ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int mod = 1000000007;
    const int N=200010;
    
    int n;
    int a[N];
    LL f[N];
    void solve()
    {
        
    	cin>>n;
    	for(int i=1;i<=n;++i) cin>>a[i];
    	f[0]=1;
    	for(int i=1;i<=n;++i){
        
    		int mx=a[i],mi=a[i];
    		for(int j=i;j>=1;j--){
        
    			mx=max(mx,a[j]);
    			mi=min(mi,a[j]);
    			if(mx-mi==i-j){
        
    				f[i]=(f[i]+f[j-1])%mod;
    			}
    		}
    	}
    	cout<<f[n]<<'\n';
    }
    int main() 
    {
        
    	ios_base :: sync_with_stdio(false);
        cin.tie(nullptr);	
        solve();
        return 0;
    }

[CSDN_2]: https://marketing.csdn.net/p/7b6697fd9dd3795a268d1a6f2fe75012
[Link 1]: https://activity.csdn.net/creatActivity?id=10221
[Link 2]: https://www.lanqiao.cn/problems/2148/learning/