已知一个长度为 N 的数组:A1, A2, A3, ...AN 恰好是 1 ∼ N 的一个排列。现在要求你将 A 数组切分成若干个 (最少一个,最多 N 个) 连续的子数组,并且每个子数组中包含的整数恰好可以组成一段连续的自然数。
例如对于 A = {1, 3, 2, 4}, 一共有 5 种切分方法:
{1}{3}{2}{4}:每个单独的数显然是 (长度为 1 的) 一段连续的自然数。
{1}{3, 2}{4}:{3, 2} 包含 2 到 3,是 一段连续的自然数,另外 {1} 和 {4} 显然也是。
{1}{3, 2, 4}:{3, 2, 4} 包含 2 到 4,是 一段连续的自然数,另外 {1} 显然也是。
{1, 3, 2}{4}:{1, 3, 2} 包含 1 到 3,是 一段连续的自然数,另外 {4} 显然也是。
{1, 3, 2, 4}:只有一个子数组,包含 1 到 4,是 一段连续的自然数。
先准备输入代码,n是数字数组长度,nums以1到n为索引方便辨认
int MOD = 1000000007; // 输入数据 Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] nums = new int[n+1]; for (int i = 1; i <= n; i++) { nums[i] = sc.nextInt(); }
使用动态规划定义数组f[n+1] f[0] = 1;
使用索引i表示以i结尾的区间的切分方式数
i是开始切分的left索引,j是right索引,如果区间长度等于区间内最大值和最小值得差,则说明连续,可以让以j结尾的方法数加上i-1的方法数
int[] f = new int[n+1]; f[0] = 1; for(int i=1; i<=n;i++){ int max = nums[i]; int min = nums[i]; for(int j=i;j<=n;j++){ max = Math.max(max,nums[j]); min = Math.min(min,nums[j]); if(j - i + 1 == max - min + 1){ f[j] = (f[j]+f[i-1])%MOD; } } }
标签:2022,真题,int,自然数,蓝桥,切分,连续,数组,一段 From: https://www.cnblogs.com/zhexian233/p/17143018.html