[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; }
发表评论