POJ 3017 Cut the Sequence

单调队列+平衡树(？)的好题...

好吧虽然这题的数据用平衡树的O(nlgn)比不用的O(n²)至少慢好5,6倍

题解什么的见一篇叫《用单调性优化动态规划》的论文

http://poj.org/problem?id=3017

O(n²)：

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
typedef long long int64;
int64 lim,sum[200000],fx[200000];
int a[200000],f=0,r=0,q[200000],n;

int main(){
	freopen("in","r",stdin);
	scanf("%d %lld",&n,&lim);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		sum[i]=sum[i-1]+a[i];
	}
	int last=1;

	for(int i=1;i<=n;i++){
		fx[i]=10000000000000;
		while(sum[i]-sum[last-1]>lim)	last++;
		if(last>i){
			printf("-1\n");
			return 0;
		}
		while(f!=r&&q[f]<last) f++;
		while(f!=r&&a[q[r-1]]<a[i])	r--;
		q[r++]=i;
		for(int j=f;j<r-1;j++)	fx[i]=min(fx[i],fx[q[j]]+a[q[j+1]]);
		fx[i]=min(fx[i],fx[last-1]+a[q[f]]);
	}
	printf("%lld\n",fx[n]);
	return 0;
}

O(nlgn)：

# include <cstdio>
# include <cstring>
# include <set>
# include <algorithm>
using namespace std;
typedef long long int64;
int64 lim,sum[200000],v[200000],tmp,fx[200000];
int a[200000],f=0,r=0,q[200000],n;

int main(){
	freopen("in","r",stdin);
	scanf("%d %lld",&n,&lim);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		sum[i]=sum[i-1]+a[i];
	}
	int last=1;

	multiset<int64> t;
	for(int i=1;i<=n;i++){
		fx[i]=100000000000000;
		while(sum[i]-sum[last-1]>lim)	last++;
		if(last>i){
			printf("-1\n");
			return 0;
		}
		while(f!=r&&q[f]<last)	t.erase(t.find(v[f++]));
		while(f!=r&&a[q[r-1]]<a[i])	t.erase(t.find(v[r-1])),r--;
		if(f!=r){
			tmp=fx[q[r-1]]+a[i];
			if(tmp>v[r-1]){
				t.erase(t.find(v[r-1]));
				t.insert(tmp);
				v[r-1]=tmp;
			}
		}	
		if(f!=r){
			tmp=*(t.begin());
			fx[i]=min(fx[i],tmp);
		}
		fx[i]=min(fx[last-1]+(f==r?a[i]:a[q[f]]),fx[i]);
		t.insert(fx[i]);q[r]=i;v[r++]=fx[i];
	}
	printf("%lld\n",fx[n]);
	return 0;
}

用平衡树时注意点：

每次塞进树里的那个值是由fx(x)+max(x,i)控制

队尾删元素后要更新最末端的数的值的max(x,i)部分

这个可以采用假设max(x,i)为a[i]，算出新值来与原值比较，取较大数完成

而计算出fx(i)后要将fx(i)塞入树中，此时可视为此值的max(x,i)部分为0