我自己测试，在sum极大和数列单调降序时卡了15.883秒--!


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100010
#define mid ((l+r)>>1)
#define ls (rt<<1)
#define rs (rt<<1|1)
ll tree[N*4];
ll dp[N],a[N],n,m;
void build(int rt,int l,int r){
	if(l==r) { tree[rt]=a[l];return ;}
	build(ls,l,mid);build(rs,mid+1,r);
	tree[rt]=max(tree[ls],tree[rs]);
}
ll quiry(int rt,int l,int r,int a,int b){
	if(a==l&&r==b)  return tree[rt];
	if(b<=mid) return quiry(ls,l,mid,a,b);
	else if(a>mid) return quiry(rs,mid+1,r,a,b);
	else return max(quiry(ls,l,mid,a,mid),quiry(rs,mid+1,r,mid+1,b));
}
int main(){
	while(cin>>n>>m){
		int i,j;
		bool flag=false;
		for(i=1;i<=n;i++){
			scanf("%lld",&a[i]);
			if(a[i]>m) flag=true;
		}
		if(flag) { cout<<"-1"<<endl;continue;}
		memset(tree,0,sizeof(tree));
		build(1,1,n);
		memset(dp,0x3f,sizeof(dp));
		dp[0]=0;
		ll sum=0,MAX=0;
		for(i=1;i<=n;i++){
			sum+=a[i];
			if(sum>m) break;
			MAX=max(MAX,a[i]);
			dp[i]=MAX;
		}
		//int p=i--;
		//sum=a[i];
		int p=2;
		sum=a[1];
		dp[1]=a[1];
		for(i=1;i<=n;i++){
			MAX=0;
			for(j=i+1;j<=p;j++){
				if(a[j]>=a[i]) break;
				MAX=max(MAX,a[j]);
				dp[j]=min(dp[j],dp[i]+MAX);
			}
			sum-=a[i];
			MAX=0;
			for(;p<=n;p++){
				if(sum+a[p]>m) break;
				//MAX=max(MAX,a[p]);
				MAX=quiry(1,1,n,i+1,p);
				sum+=a[p];
				dp[p]=min(dp[p],dp[i]+MAX);
			}
		}
		cout<<dp[n]<<endl;
	}
	return 0;
}
/*
8 17
2 2 2 8 1 8 2 1
*/

• 错了，是一分钟。。。 (0) qwg 2014-06-05 22:24:21