[TJOI2011]書架

題目大意：

輸入兩個正整數n，m，在輸入n個數，将這n個數分成連續的若幹段，滿足每一段之和不超過m，同時使得這若幹組中，每組的最大值之和最小，輸出這個最小值。

對于30%的資料，n ≤ 1,000。

對于100%的資料，n ≤ 100,000，hi ≤ 10,000，m ≤ 1,000,000,000。

30%做法：

沒學過dp的童鞋可以移步到其他題目去了這道題并不那麼适合你......

30%的資料，n<=1000,可以雙重循環枚舉更新，設a數組為題目中讀入的數組，f【i】為考慮将前i本書都放下的最小花費，明顯可以由前面的f【j】轉移過來，且貢獻是放放f【j】+max（a【k】（j+1<=k<=i））。 可以先做個字首和，以便于O（1）判斷i，和j之間的書的總量是否超過m，當然也可以從i往前掃，每次考慮完一個j就加上啊a【j】。複雜度O（n^2）,完全不虛。

100%做法：

考慮在30%做法的基礎上進行優化，首先我們可以發現一個很顯而易見的特點，就是f數組的值是單調不下降的，因為能放下前i+1本書的方案都必然放下了前i本書，花費自然不會比前i本書的少。是以這就可以用一些奇奇怪怪的玄學方法或者資料結構維護dp。首先要普及一種單調隊列求區間最小值的方法：比如對于一個長度為6的序列1 5 2 1 4 3，我們要求出每3個數的最小值，我們可以維護一個單調下降的序列同時維護它的下标：一開始序列為空，然後操作到1，

序列：  值：  1

          下标： 1

然後操作到 5，這時候從隊尾往前掃，掃到第一個碰到大于它的數或隊列為空時停止：

序列：  值：  5

          下标： 2

（5比1大，将1彈出隊列，隊列為空，然後将5加入隊列）

操作到2，

序列：  值：  5     2

          下标： 2     3

操作到1：

序列：  值：  5     2     1

          下标： 2     3     4

操作到4,

4比1大，将1彈出，比2大，再将2彈出，當新加入的值無法彈出其他數并加入隊列以後，還有一步很重要的操作，就是判斷一下隊頭的數的下标是否有超出求值範圍，若現在加入了第i個數，考慮的是連續k個數的最大值，那麼這時要考慮的是第i-k+1個數到第i個數的最大值，也就是說如果隊頭的數的下标要小于i-k+1，就要彈掉，這時5的下标是2，而我們已經加入的第5個數，也就是考慮的是3到5的最大值，5的下标過小，是以可以彈掉。

序列：  值：  4

          下标： 5

操作到1:

序列：  值：  4     1

          下标： 5     6

這時，我們就發現，每在隊列裡加入一個數時，需要3步操作：

1.先從隊列的尾部往前一直彈掉比新加的數小的數

2.将新加的數加入隊尾

3.判斷隊頭的數是否需要彈掉

這樣，不難發現，當我們插入第i個數的時候，以第i個數為結尾的連續k個數的最大值便是目前隊頭的數。

那麼，為什麼這個時間複雜度是O（n）的呢？首先，“3.判斷隊頭的數是否需要彈掉”這一步最多隻會彈一個數，然後，雖然“1.先從隊列的尾部往前一直彈掉比新加的數小的數”這個操作一步可能會彈掉很多個數，但是一個n個數的序列，一共才n個數進入單調隊列，額每彈一個數隊列裡就少了一個數，是以雖然插入一個數可能會彈掉很多個數，可是彈掉數的總數是不會超過n的，是以這是一個O（n）的算法。

然後，這道題的dp就可以用單調隊列+線段樹維護dp了，我們考慮枚舉到了求f【i】的值，由于f數組具有單調性，是以假設f【j】和f【k】都可以對f【i】進行貢獻，且第k+1個數到第i個數的最大值和第j+1個數到第i個數的最大值相等，那我們隻需要取j和k中下标較小的對i進行貢獻，換句話說，我們隻需要維護能貢獻到i的每種到i的最大值不同的j的下标最小的那一個就可以了，然後用個單調隊列維護，操作和上面類似，而線段樹是用來維護每一個單調隊列中的j的貢獻，可以快速查詢最小值。具體還有些細節，就留給讀者們自己思考了。

                                                                              推薦番：《約會大作戰》

上代碼：

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
struct dat
{int val,wei,ff;};
dat line[100005];
int tre[500005],book[100005],qian[100005],f[100005],n,m,h,t,head,tail,s,p,ma;
void jia(int wei,int val,int l,int r,int root)
{
	if (l==r){tre[root]=val;return;}
	int mid=(l+r)/2;
	if (wei<=mid)jia(wei,val,l,mid,root*2);
	else jia(wei,val,mid+1,r,root*2+1);
	tre[root]=min(tre[root*2],tre[root*2+1]);
}
int fid(int h,int t,int l,int r,int root)
{
	if (l==r){return tre[root];}
	if (h<=l && t>=r)return tre[root];
	int mid=(l+r)/2,mm=1000000007;
	if (h<=mid)mm=fid(h,t,l,mid,root*2);
	if (t>=mid+1) mm=min(mm,fid(h,t,mid+1,r,root*2+1));
	return mm;
}
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&book[i]);
	}
	h=1;head=1;tail=0;
	while (t<n && s+book[t+1]<=m)
	{
	     t++;s+=book[t];qian[t]=1;ma=max(ma,book[t]);f[t]=ma;
	     while (tail>0 && book[t]>=line[tail].val)tail--;
	     tail++;line[tail].val=book[t];line[tail].wei=t;line[tail].ff=line[tail-1].wei;
	     jia(tail,f[line[tail-1].wei]+book[t],1,n,1);
	}
	for (int i=t+1;i<=n;i++)
	{
		s+=book[i];
		while (s>m){s-=book[h];h++;}
		qian[i]=h;
	}
	 for (int i=t+1;i<=n;i++)
	 {
	 	while (line[head].wei<qian[i] && head<=tail){line[head].wei=0;head++;}
	 	if (line[head].ff<qian[i]-1){line[head].ff=qian[i]-1;jia(head,f[qian[i]-1]+line[head].val,1,n,1);}
	 	while (tail>=head && book[i]>=line[tail].val){tail--;}
	 	tail++;line[tail].val=book[i];line[tail].wei=i;line[tail].ff=max(line[tail-1].wei,qian[i]-1);
	 	jia(tail,f[line[tail].ff]+book[i],1,n,1);
	 	f[i]=fid(head,tail,1,n,1);
	 }
	 cout<<f[n];
}