!!!不正确,以后再修改
(1)
要切分n个元素的数组,有n-1个空隙,共2的n-1次方种切法;
f(i)表示所有前i个数划分方案的集合(每个小于M就可以);有2^(i-1)种;
f(i)的属性:最大值的最小和
最终求:f(n)
(2)
以最后一个划分区间的长度k(amax是定值),给f(i)f分类,再找最小(前面已有)
(3)优化
原:从小到大枚举k(倒着找,直到和大于m不再枚举)+在k中遍历+遍历i;
从小到大枚举k时顺便找最小;
如果不划分到k的最大,那就依次找往后第二、三大的amx,当i往后走,j也一定往后走(j是区间k的左端点)----amax+f(j);
区间扩大时,amax用单调队列移动
java 代码
//不正确,以后再修改
import java.util.*;
import java.io.*;
public class Main{
static int N=10010;
static long[] dp=new long[N];
static int[] q=new int[N];
static int[] w=new int[N];
static int sum=0;//sum是区间和
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
long m=scan.nextLong();
for(int i=1;i<=n;i++){
w[i]=scan.nextInt();
if(w[i]>m){
System.out.println("-1");
return;
}
}
int hh=0,tt=-1;
for(int i=1,j=1;i<=n;i++){
sum+=w[i];
//控制和不大于m
while(sum>m){
sum-=w[j++];
}
//找amax
if(hh<=tt&&q[hh]<j)hh++;
while(hh<=tt&&w[q[tt]]<w[i])tt--;
q[++tt]=i;
dp[i]=dp[j-1]+w[q[tt]];
}
System.out.println(dp[n]);
}
}