用asp.net做的网站,网页设计实训报告,汽车品牌推广方案,网站js特效悬浮框题目链接#xff1a;
蓝桥杯2022年第十三届省赛真题-数组切分 - C语言网 (dotcpp.com) 1.数组切分 - 蓝桥云课 (lanqiao.cn)
这道题C语言网数据会强一些。 说明#xff1a;
对于一个切分的子数组#xff0c;由于数组是1-N的一个排列#xff0c;所以每个数唯一 可以用子…题目链接
蓝桥杯2022年第十三届省赛真题-数组切分 - C语言网 (dotcpp.com) 1.数组切分 - 蓝桥云课 (lanqiao.cn)
这道题C语言网数据会强一些。 说明
对于一个切分的子数组由于数组是1-N的一个排列所以每个数唯一 可以用子数组最大值-最小值子数组长度-1子数组右端点索引 -左端点索引1-1来判断 。 尝试题目求什么我们就设dp数组为 什么那么设f[i]为 前i个数能有f[i]种方案 观察样例手工计算 A1324 i为1时方案为 {1} i为2时方案为 {1}{3} 而{13}不行 i为3时方案为 {1}{3}{2}{1}{32}{132} 而{13}{2}不行 i为4时方案为 {1}{3}{2}{4}{1}{32}{4}{132}{4} {1}{324}{1324} 而{1}{3}{24}{13}{2}{4}不行 发现当加入第i个数是时如果把第j个数和第i个数划成一组如果这个划分合法 那么他就能和f[j-1] 的每个方案 组合成 合法方案于是累加上[ji]划分合法时每个 f[j-1]就是f[i]的值 。 注意如果1到i所有数在一个切分里能组成合法的区间这时的j-1为0 ,故初始化f[0]1
在c语言网用scanf输入才能ac用cin有一个测试点过不了。
代码
#include bits/stdc.h
//#define int long long
using namespace std;
const int N1e510;/*对于一个切分的子数组由于数组是1-N的一个排列所以每个数唯一可以用子数组最大值-最小值子数组长度-1子数组右端点索引-左端点索引1-1来判断 尝试题目求什么我们就设dp数组为 什么那么设f[i]为 前i个数能有f[i]种方案 观察样例手工计算 A1324 i为1时方案为 {1} i为2时方案为 {1}{3} 而{13}不行 i为3时方案为 {1}{3}{2}{1}{32}{132} 而{13}{2}不行 i为4时方案为{1}{3}{2}{4}{1}{32}{4}{132}{4} {1}{324}{1324} 而{1}{3}{24}{13}{2}{4}不行 发现当加入第i个数是时如果把第j个数和第i个数划成一组如果这个划分合法那么他就能和f[j-1] 的每个方案 组合成 合法方案于是累加上[ji]划分合法时每个f[j-1]就是f[i]的值 。注意如果1到i所有数在一个切分里能组成合法的区间这时的j-1为0 ,故初始化f[0]1*/int a[N];
//表示前i个数能有f[i]种切分方法
int f[N];
int mod1000000007;
int n;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(int i1;in;i){// cina[i];//开long long 之后 用scanf格式控制符要用lld//用scanf要关掉上面的ios语句 scanf(%d,a[i]); }//需要初始化0处为1因为如果1到i所有数在一个切分里能组成合法的区间//这时的j-1为0 ,故f[0]1f[0]1;f[1]1;for(int i2;in;i){//序列最小值减最大值等于序列长度-1即为自然数 int maa[i],mia[i];for(int ji;j1;j--){//维护最值 mamax(ma,a[j]),mimin(mi,a[j]);if(ma-mii-j){f[i](f[i]f[j-1])%mod;}}}coutf[n];return 0;
}
