题目概述
你需要将一个长度为 \(n\) 的序列 \(A\) 分成若干段，满足每段中数字之和 \(\leq m\)，每段将这一段的最大值作为他的贡献，求他们贡献之和的最小值。
分析
蓝书好题！这是一道例题。
不难设 \(f_i\) 表示前 \(i\) 个数分成若干段所得到的最小答案。
显然转移有：
\[f_i=\min_{j\in[0,i-1],\sum_{k=j + 1}^i a_k\leq m}\{f_j+\max_{k\in[j+1,i]}a_k\}
\]
直接转移是 \(\mathcal{O}(n^2)\) 的。
\(dp\) 的转移优化的指导思想就是及时排除不可能的决策。
我们不难根据题目的意思发现：\(f_i\) 是单调不降的。
若 \(a_{j}\leq a_{j+1}\)。那么显然：
\[f_{j-1}+\max\leq f_j+\max
\]
也就是说我们维护一个依据坐标的 \(a_x\) 单调递减的队列即可。
当然我的转移还有可能来自最远的那个点。
代码
时间复杂度 \(\mathcal{O}(n\log n)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <set>
#define int long long
#define N 100005
using namespace std;
int n,f[N],a[N],m,sum[N];
int head,tail,q[N << 2];
multiset<int> st;
signed main(){cin >> n >> m;for (int i = 1;i <= n;i ++) scanf("%lld",&a[i]),sum[i] = sum[i - 1] + a[i];for (int i = 1;i <= n;i ++)if (a[i] > m) return cout << -1,0;head = 1,tail = 0;for (int i = 1;i <= n;i ++) {while(head <= tail && sum[i] - sum[q[head]] > m) st.erase(f[q[head]] + a[q[head + 1]]),head ++;while(head <= tail && a[i] > a[q[tail]]) st.erase(f[q[tail - 1]] + a[q[tail]]),tail --;//纯粹更新fj+mx中的mx，因为你mx变大了那么肯定是越前面的点相较于当前的队尾的点更优啊if (head <= tail) st.insert(f[q[tail]] + a[i]);q[++tail] = i;int l = 0,r = i - 1,res = 0;while(l <= r) {int mid = l + r >> 1;if (sum[i] - sum[mid] <= m) res = mid,r = mid - 1;else l = mid + 1;}f[i] = f[res] + a[q[head]];if (!st.empty()) f[i] = min(f[i],*st.begin());}cout << f[n];return 0;
}//这题不难想到也可以用线段树优化dp
代码中的注释很精髓的。