[POJ 3017] Cut the Sequence【DP+单调队列+multiset】
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
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;
}
发表评论