# [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[ i ] = min{ dp[ j ] + max{ a[ k ] } }, 其中 j < k ≤ i∑ a[ k ] ≤ M

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

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

## 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
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

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