题意
| Time Limit: 2000MS | Memory Limit: 131072K | |
| Total Submissions: 12238 | Accepted: 3809 |
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 contains N 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
将一个由N个数组成的序列划分成若干段，要求每段数字的和不超过M，求【每段的最大值】的和 的最小的划分方法，输出这个最小的和。
分析
很久以前某搬题人出的考试题，竟然是POJ原题！还是我做的题太少了。参照Excelsior_kereo的题解。
设dp[i]为前i个数取得的最小和，那么我们可以有递推公式：dp[i]=min(dp[i],dp[j]+max(a[j+1],a[j+2],...,a[i])) ，其中j<=i 且sum[j]-sum[i-1]<=m。 由于a数组均大于0，那么可以发现数组dp必然是非递减的。 设a[j+1],a[j+2],...,a[i]中的最大值下标为k，由dp的非递减性，dp[j+1]+a[k]<=dp[j+2]+a[k]<=...<=dp[k-1]+a[k].所以我们取dp[j+1]+a[k],也就是说如果某一段到当前位置i的最大值都一样，取最靠前的即可。那么可以联想到单调队列，维护一个递减的队列，存的是符合要求的某一段的最大值。但是需要注意！队首元素不一定是最优的，由于队列的递减性质，队列中的所有元素都有可能组成最优解。所以用一棵平衡树（multiset）维护。
时间复杂度\(O(n \log n)\)
代码
#include<iostream>
#include<set>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
using namespace std;
co int N=1e5+1;
int n,q[N];
ll m,a[N],f[N];
multiset<ll> s;
multiset<ll>::iterator it;
int main(){
read(n),read(m);
for(int i=1;i<=n;++i)
if(read(a[i])>m) return puts("-1"),0;
int t=1,l=0,r=0;
ll tot=0;
for(int i=1;i<=n;++i){
tot+=a[i];
while(tot>m) tot-=a[t++];
while(l<r&&q[l]<t)
if(++l<r&&(it=s.find(f[q[l-1]]+a[q[l]]))!=s.end()) s.erase(it);
while(l<r&&a[q[r-1]]<=a[i])
if(l<--r&&(it=s.find(f[q[r-1]]+a[q[r]]))!=s.end()) s.erase(it);
if(l<r) s.insert(f[q[r-1]]+a[i]);
q[r++]=i;
f[i]=f[t-1]+a[q[l]];
if(s.begin()!=s.end()) f[i]=min(f[i],*s.begin());
}
printf("%lld\n",f[n]);
return 0;
}