「POJ3017」Cut the Sequence

题意：一个长度为 $n(n\le 10 ^5)$ 数组 $a$，要求把它划分成连续若干个部分，每部分的和不超过 $m$，且使得所有部分的最大值的和最小，输出最小的最大值之和。

一道很明显的 dp 题。

状态：$f[i]$ 表示将前 $i$ 个数划分后，得到的最小的最大值之和。

很容易可以得到状态转移方程：

$$f[i]=\min(f[j]+\max (a[j+1],a[j+2],···,a[i]))(j<i)$$

状态的时间复杂度为 $O(n)$，现在主要考虑如何优化转移。

容易发现，转移方程保证 $f[i]$ 一定是单调不下降的。所以如果在 $a[j+1\sim i]$ 中最大的数为 $a[k]$，我们只需要找出在它的管辖范围内最前面的点即可。

意思就是，假设 $x$ 为 $[j,k-1]$ 中的任意一个下标，那么 $a[k]$ 依然是 $a[x+1 \sim i]$ 中的最大值，此时保证：

$$f[j]+a[k]\le f[j+1]+a[k]\le ···\le f[k-1]+a[k]$$

此时很明显取最前面的 $f[j]$ 能得到最小。

所以如何找最大的 $a[k]$，我们由一个单调队列维护即可，但是这不能保证 $f[j]+a[k]$ 最小(因为还可能存在 $x\in [k,p-1]$ 的情况，此时可能 $f[k]+a[p]$ 最优，$a[p]$ 为 $a[x+1\sim i]$ 的最大值)，所以我们还要用 multiset 维护 $f[j]+a[k]$。(P.S：可以发现 $j$ 与 $k$ 在单调队列中相邻，因为下一个决策为 $f[k]+a[p]$，队列中依次为 $j,k,p$。_{感性理解，管辖范围之外的第一个})

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<set>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=1e5+101;
long long n,m;
long long a[maxn],f[maxn],sum[maxn];
long long q[maxn],k,head,tail;//单调队列，维护最大a[i]的下标
multiset<long long> s;//维护f[j]+a[k](满足a[k]为[j+1,i]最大)
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		if(a[i]>m)
		{
			printf("-1");
			return 0;
		}
		sum[i]=sum[i-1]+a[i];
	}
	head=1;
	tail=0;
	k=0;
	for(int i=1;i<=n;i++)
	{
		while(sum[i]-sum[k]>m)
			k++;//保证[k,i]和小于m
		while(head<=tail&&q[head]<=k)//删除不合法决策
		{
			if(head<tail)
				s.erase(a[q[head+1]]+f[q[head]]);
			head++;
		}
		while(head<=tail&&a[q[tail]]<=a[i])//维护单调性
		{
			if(head<tail)
				s.erase(a[q[tail]]+f[q[tail-1]]);
			tail--;
		}
		q[++tail]=i;
		if(head<tail)
			s.insert(a[i]+f[q[tail-1]]);//每访问一次i,添加相应决策
		f[i]=f[k]+a[q[head]];//最大值a[q[head]]对应的最优决策
		if(head<tail)
			f[i]=min(f[i],*s.begin());//其他决策
	}
	printf("%lld",f[n]);
	return 0;
}