题意分析

将一个长度为$n$,的数组分成$m$份（不分首尾） 区间$l~r$的值为：

求这些值相乘的最大和最小值

思路解析

深搜枚举所有可能的区间划分，统计最值 再用可行性剪枝优化。

代码

1.边界

if(cnt==m-1){//特殊处理最后一次
	int res=0;
	for(int j=last+1;j<=n;j++){
		res+=a[j];
	}
	res=(res%10+10)%10;
	maxx=max(maxx,sum*res);
	minn=min(minn,sum*res);
	return ;
}

2.循环

for(int i=last+1;i<=n-m+cnt+1;i++){
		res+=a[i];
		res=(res%10+10)%10;
		dfs(i,cnt+1,sum*res);
	}

3.优化

if(sum>=minn and sum*f[m-cnt]<=maxx)return ;//不可能被选的情况