地方门户网站设计,工作指令,wordpress带手机验证码,电子商务网站建设与运营问题描述 已知一个长度为 N 的数组: A1,A2,A3,...AN 恰好是1~ N的一个排列。现 在要求你将 4 数组切分成若干个 (最少一个,最多 N 个)连续的子数组,并且 每个子数组中包含的整数恰好可以组成一段连续的自然数。 例如对于 4 1,3,2,4,一共有 5 种切分方法: 1324:每个单独的数显然…问题描述 已知一个长度为 N 的数组: A1,A2,A3,...AN 恰好是1~ N的一个排列。现 在要求你将 4 数组切分成若干个 (最少一个,最多 N 个)连续的子数组,并且 每个子数组中包含的整数恰好可以组成一段连续的自然数。 例如对于 4 1,3,2,4,一共有 5 种切分方法: 1324:每个单独的数显然是(长度为 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 。第二行包含 N 个整数,代表 4 数组。 输出格式 输出一个整数表示答案。由于答案可能很大所以输出其对1000000007 取 模后的值 样例输入 样例输出 评测用例规模与约定 对于 30% 评测用例,1N20. 对于 100% 评测用例,1N10000 运行限制 最大运行时间:5s。 最大运行内存:512M
import java.util.Scanner;
public class Main {static int mod 1000000007;public static void main(String[] args) {Scanner scannew Scanner(System.in);int nscan.nextInt();int[] anew int[n1];for (int i1;in;i) a[i]scan.nextInt();//dp[i]以a[i]结尾的切分合法数组的方法数量int[] dpnew int[n1];dp[0]1;//初始化for (int i1;in;i){int maxInteger.MIN_VALUE,minInteger.MAX_VALUE;//注意初始化max是小的min是大的for (int ji;j0;j--){max Math.max(max,a[j]);min Math.min(min,a[j]);if (max-mini-j) dp[i](dp[i]dp[j-1])%mod;}}System.out.println(dp[n]);}
}
