外贸soho通过网站开发客户,wordpress 餐饮 主题,广东东莞人才网招聘网,深圳个人形象设计工作室数组切分
题目分析
这里要搞清楚一个点就是满足区间内数字是连续数字的区间有什么样的特点#xff0c;既然数字连续重新排列后的数字为n,n1,n2,n3,n4,…nlen#xff0c;则最大数字和最小数字之差恰好是区间长度减1#xff0c;即nlen-nlen#xff0c;同样因为下标也是连续…数组切分
题目分析
这里要搞清楚一个点就是满足区间内数字是连续数字的区间有什么样的特点既然数字连续重新排列后的数字为n,n1,n2,n3,n4,…nlen则最大数字和最小数字之差恰好是区间长度减1即nlen-nlen同样因为下标也是连续数字那么左端点和右端点的下标之差也是区间长度减1所以最大数字和最小数字之差恰好是左端点和右端点的下标之差。
定义dp[i]表示以a[i]结尾的区间能够被划分的区间的个数那么dp[i]可以从 d p [ j − 1 ] ( j i ) dp[j-1](ji) dp[j−1](ji)转移过来的条件是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[n1];int mod 1000000007;for (int i 1; i a.length; i) {a[i] scanner.nextInt();}int dp[] new int[n1];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-mini-j) {dp[i] (dp[i] dp[j-1])%mod;}}}System.out.println(dp[n]);
}
}
