poj 3017 Cut the Sequence dp+单调队列优化

题意：

给大小为n的数组a[n]以及数m，求将a[n]划分为任意个部分后每部分最大值的最小和。比如 n=8,m=17 a[n]=2,2,2,8,1,8,2,1。答案是12，对应的划分为2.2.2。8,1,8。2,1。

思路：

dp,方程为 dp[i] = min( dp[j] + max(a[j+1,j+2,...i]) )  (j<i, sum(a[j+1,j+2,...i])<=m)，这样的复杂度是n^2的，求max(j+1,j+2,...i)的步骤可以用单调队列优化。

代码：

//poj 3017
//sepNINE
#include <iostream>
using namespace std;
const int maxN = 100024;

__int64 m,a[maxN],dp[maxN];
int n,q[maxN];

__int64 solve()
{
	int i,j,k,front,rear;
	__int64 sum;
	
	for(i=1; i<=n; ++i)
		if(a[i]>m)
			return -1;
	
	front=0;
	rear=-1;	
	sum=dp[0]=0;
	
	for(i=k=1; i<=n; ++i){
		sum+=a[i];
		for(; sum>m ; ++k)
			sum-=a[k];
		for(; front<=rear&&q[front]<k; ++front);
		for(; front<=rear&&a[q[rear]]<=a[i]; --rear);
		q[++rear]=i;
		dp[i]=dp[k-1]+a[q[front]];	
		for(j=front; j<rear; ++j)
			dp[i]=min(dp[i], dp[q[j]]+a[q[j+1]]);
	}
	
	return dp[n];
}

int main()
{
	int i;
	scanf("%d%I64d", &n, &m);
	for( i=1; i<=n; ++i )
		scanf("%I64d", &a[i]);
	printf("%I64d", solve());	
	return 0;	
}