蓝桥杯——数组切分

本文主要是介绍蓝桥杯——数组切分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数组切分

题目分析

这里要搞清楚一个点就是满足区间内数字是连续数字的区间有什么样的特点，既然数字连续重新排列后的数字为n,n+1,n+2,n+3,n+4,…n+len，则最大数字和最小数字之差恰好是区间长度减1，即n+len-n=len，同样因为下标也是连续数字，那么左端点和右端点的下标之差也是区间长度减1，所以最大数字和最小数字之差恰好是左端点和右端点的下标之差。

定义dp[i]表示以a[i]结尾的区间能够被划分的区间的个数，那么dp[i]可以从$dp[j-1](j<i)$转移过来的条件是a[j]~a[i]这个区间是一个连续区间。

题目代码

import java.util.Scanner;
public class Main{
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int a[] = new int[n+1];int mod = 1000000007;for (int i = 1; i < a.length; i++) {a[i] = scanner.nextInt();}int dp[] = new int[n+1];dp[0] = 1;for (int i = 1; i < dp.length; i++) {int max = a[i];int min = a[i];for (int j = i; j > 0; j--) {max = Math.max(a[j], max);min = Math.min(a[j], min);if(max-min==i-j) {dp[i] = (dp[i] + dp[j-1])%mod;}}}System.out.println(dp[n]);
}
}

这篇关于蓝桥杯——数组切分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---