[POJ 3017] Cut the Sequence【DP+单调队列+multiset】

  • 2018-01-26
  • 0
  • 0

Problem:

Time Limit: 2000MS Memory Limit: 131072K

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

POJ Monthly--2006.09.29, zhucheng

Solution:

本题是较难的 DP 优化问题,采用了高级数据结构优化。

状态转移方程比较简单,只要令 dp[i] 为在前 i 个数中分组后最小的每组最大值总和,则

  • dp[ i ] = min{ dp[ j ] + max{ a[ k ] } }, 其中 j < k ≤ i∑ a[ k ] ≤ M

但是即使 max{ a[ k ] }ST 表能 O(1) 询问,总复杂度还是达到了 O(N2),TLE。

由于 max{ a[ k ] } 一项与 i 有关,不能直接将等式右边扔进单调队列来计算最优的 j。

但是间接地使用单调队列是可行的。

我们假设以 i 为右端点的一组值左端点至多达到 lb

此时可以用单调队列 q[fr..re] 维护一个合法严格递减的 a[] 下标,那么最优解的一个可能

  • dp[ i ] ≤ dp[ lb - 1 ] + a[ q[ fr ] ] …… (1)

但是最优解不一定是取 [lb, i] 的整个区间。

我们发现,由于 dp[] 的单调递增性质,若表达式 dp[ p ] + a[ q ] 中有 a[ p ] < a[ q ],则不如把 a[p] 分到 a[q] 所在的一组中,此时 dp[ p - 1 ] + a[ q ] 一定更优

我们又发现,在单调队列中,q[ s ] < q[ s + 1 ]a[ q[ s ] ] > a[ q[ s + 1 ] ]

所以最优解的形式一定是

  • dp[ i ] ≤ dp[ q[ s ] ] + a[ q[ s + 1 ] ], 其中 s ∈ [fr, re - 2] …… (2)

综合 (1)(2) 两式即为答案。

我们可以使用 multiset 来与单调队列同步维护 (2) 式,总复杂度降为 O(NlogN)

觉得比较难,看了题解。。我还是太弱了。。

Code: O(NlogN) [3024K, 1157MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;

int N;
ll M, a[100005], sum[100005];
ll dp[100005];
int q[100005], fr, re, lb;
multiset<ll> s;

int main(){
	scanf("%d%lld", &N, &M);
	for(register int i = 1; i <= N; i++)
		scanf("%lld", a + i), sum[i] = sum[i - 1] + a[i];
	fr = re = 0, lb = 1;
	for(register int i = 1; i <= N; i++){
		if(a[i] > M) {puts("-1"); return 0;}
		while(sum[i] - sum[lb - 1] > M) lb++;
		while(fr < re && q[fr] < lb){
			if(fr + 1 < re) s.erase(dp[q[fr]] + a[q[fr + 1]]);
			fr++;
		}
		while(fr < re && a[i] >= a[q[re - 1]]){
			if(fr + 1 < re) s.erase(dp[q[re - 2]] + a[q[re - 1]]);
			re--;
		}
		if(fr < re) s.insert(dp[q[re - 1]] + a[i]);
		q[re++] = i;
		if(fr < re){
			dp[i] = dp[lb - 1] + a[q[fr]];
			if(fr + 1 < re) dp[i] = min(dp[i], *s.begin());
		}
	}
	printf("%lld\n", dp[N]);
	return 0;
}

评论

还没有任何评论,你来说两句吧



新博客地址: darkleafin.cf

常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai