Description
Given an integer sequence { an } of length N, you are to cut the sequence into several parts every one of which is a consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. You are to find a cutting that minimizes the sum of the maximum integer of each part.
Input
The first line of input contains two integer N (0 < N ≤ 100 000),M. The following line containsN integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.
Output
Output one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output −1.
Sample Input
8 17
2 2 2 8 1 8 2 1
Sample Output
12
Hint
Use 64-bit integer type to hold M.
Source
POJ Monthly--2006.09.29, zhucheng题意：给定一个有n个非负整数的数列a，要求将其划分为若干个部分，使得每部分的和不超过给定的常数m，并且所有部分的最大值的和最小。其中n<=105。
分析：可以看出决策区间是具有单调性的，我们可以用一个双端队列来维护决策区间，但是这题最优决策在决策区间中的位置并不确定，而且最头的决策还需要特判，所以用一个set来维护最优决策的值。
#include <map>
#include <set>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <utility>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int n,tail;
long long m,sum[100007],a[100007],dp[100007];
deque <int> q ;
multiset <long long> f;
int main()
{
scanf("%d%I64d",&n,&m);
for(int i = 1;i <= n;i++)
{
scanf("%I64d",&a[i]);
sum[i] = sum[i-1] + a[i];
}
memset(dp,INF,sizeof(dp));
dp[0] = 0;
for(int i = 1;i <= n;i++)
{
while(sum[i] - sum[tail] > m) tail++;
if(tail == i)
{
cout<<-1<<endl;
return 0;
}
while(!q.empty() && sum[i]-sum[q.front()-1] > m)
{
deque <int> :: iterator it = q.begin();
if(q.size() > 1) f.erase(dp[q.front()]+a[*++it]);
q.pop_front();
}
while(!q.empty() && a[i] >= a[q.back()])
{
deque <int> :: iterator it = q.end();
it--;
if(q.size() > 1) f.erase(dp[*--it]+a[q.back()]);
q.pop_back();
}
if(!q.empty()) f.insert(dp[q.back()]+a[i]);
q.push_back(i);
if(!f.empty()) dp[i] =*f.begin();
dp[i] = min(dp[i],dp[tail]+a[q.front()]);
}
cout<<dp[n]<<endl;
}