POJ3017 Cut the Sequence

时间：2022-04-04 10:18:52

题意

Language:Default
Cut the Sequence
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;

}

相关文章