现在要建 n 栋楼，有两个限制：
限制一：第 i 栋楼最多只能建 m[i] 层；
限制二：假设现在第 i 栋楼建了 a[i] 层，那么数组 a 需要满足对于任意的 i，都满足 1 <= a[i] <= m[i]，且不能存在 j < i < k 使得 a[i] < a[j] && a[i] < a[k]
要求你最终建好的总楼层数尽可能的大，即 a[1] + ... + a[n] 尽可能大，输出数组 a。
假设我们当前在处理区间 [l, r] 内的建楼问题，并且数组 m 在区间 [l, r] 中的最小值出现在下标为 pos 的位置，我们应该让这个位置的楼层尽可能的高，所以 a[pos] = m[pos]；
为了让区间 [l, r] 满足限制二，我们要么数组 a 的 [l, pos-1] 整个区间都等于 a[pos]，要么让数组 a 的 [pos+1, r] 整个区间都等于 a[pos]，那么我们只需要在两种方案中选择最佳的那个即可。
于是，我们可以用分治来解决这个问题，一开始处理的是区间 [1,n]，然后找到最小值位置 pos，就将区间分成 [1,pos-1] 和 [pos+1,n] 两个区间，再递归的去求解，取最优解即可。
由于 n <= 1000，我们可以 O(n^2) 做，对于 找每个区间最小值的位置 这一问题，我们可以直接 O(n) 枚举去找，这样，总的复杂度就是 O(n^2)。
#include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1e6 + 5; int a[N], ans[N]; int n; pair < int, int > query(int l, int r) { /// 求解区间 [l,r] 的最小值和最小值位置 int pos = l, mi = a[l]; for(int i = l; i <= r; i++) { if(a[i] < mi) { mi = a[i]; pos = i; } } return make_pair(mi, pos); } LL solve(int l, int r) { if(l == r) { /// 递归出口 ans[l] = a[l]; return 1LL * a[l]; } if(l > r) return 0LL; pair < int, int > tmp = query(l, r); /// 找到区间 [l, r] 的最小值和最小值位置，first是最小值，second是最小值的位置 int pos = tmp.second; /// 分治求解两个区间 LL ans1 = solve(l, pos - 1) + 1LL * (r - pos + 1) * a[pos]; LL ans2 = solve(pos + 1, r) + 1LL * (pos - l + 1) * a[pos]; /// 取最优解并保存答案 if(ans1 >= ans2) { for(int i = pos; i <= r; i++) ans[i] = tmp.first; return ans1; } else { for(int i = l; i <= pos; i++) ans[i] = tmp.first; return ans2; } } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); solve(1, n); /// 分治求解 for(int i = 1; i <= n; i++) printf("%d ", ans[i]); return 0; }
这个时候再 O(n^2) 做会超时，对于 找每个区间最小值的位置 这一问题，我们考虑用线段树来维护，找最小值位置只需 O(logn)，那么总的复杂度就是 O(nlogn)。
#include <bits/stdc++.h> #define LL long long #define INF INT_MAX using namespace std; const int N = 1e6 + 5; int a[N], ans[N]; int n; pair < int, int > t[N << 2]; void build(int rt, int l, int r) { if(l == r) { t[rt] = make_pair(a[l], l); return ; } int mid = (l + r) >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); if(t[rt << 1].first <= t[rt << 1 | 1].first) t[rt] = t[rt << 1]; else t[rt] = t[rt << 1 | 1]; } pair < int, int > query(int rt, int l, int r, int L, int R) { if(L <= l && r <= R) return t[rt]; int mid = (l + r) >> 1; pair < int, int > ans = make_pair(INF, 0); if(L <= mid) { pair < int, int > tmp = query(rt << 1, l, mid, L, R); if(tmp.first < ans.first) ans = tmp; } if(R > mid) { pair < int, int > tmp = query(rt << 1 | 1, mid + 1, r, L, R); if(tmp.first < ans.first) ans = tmp; } return ans; } LL solve(int l, int r) { if(l == r) { /// 递归出口 ans[l] = a[l]; return 1LL * a[l]; } if(l > r) return 0LL; pair < int, int > tmp = query(1, 1, n, l, r);/// 找到区间 [l, r] 的最小值和最小值位置，first是最小值，second是最小值的位置 int pos = tmp.second; /// 分治求解两个区间 LL ans1 = solve(l, pos - 1) + 1LL * (r - pos + 1) * a[pos]; LL ans2 = solve(pos + 1, r) + 1LL * (pos - l + 1) * a[pos]; /// 取最优解并保存答案 if(ans1 >= ans2) { for(int i = pos; i <= r; i++) ans[i] = tmp.first; return ans1; } else { for(int i = l; i <= pos; i++) ans[i] = tmp.first; return ans2; } } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, 1, n); /// 建线段树 solve(1, n); /// 分治递归求解 for(int i = 1; i <= n; i++) printf("%d ", ans[i]); return 0; }
我们可以想象最终的 a 数组一定是类似于那种 “山峰” 的感觉，也就是说最终的 a 数组存在一个最高点，我们假设其下标为 pos，那么数组 a 在区间 [1,pos] 一定是非递减（即 a[1] <= a[2] .... <= a[pos]）的，在区间 [pos,n] 一定是非递增的（即 a[pos] >= .... >= a[n]）。那么可以枚举这个最高点的位置，确定了一个位置，其他位置就可以贪心的取最大，最后算出总和，维护一个最优解即可。
由于 n <= 1000，我们可以 O(n^2) 做，先是 O(n) 的枚举最高点的位置，再对于每个最高点，O(n) 的求出其他位置能取到的最大值，并算出总和，维护一个最优解即可。
#include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1e6 + 5; int a[N],ans[N],tmp[N]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); LL ma = 0; int ma_pos = 1; /// 定义一个最大值，和取得最大值的位置 pos for(int i = 1; i <= n; i++) { /// 枚举最高点 LL res = a[i]; tmp[i] = a[i]; for(int j = i-1; j >= 1; j--) { /// 贪心的求其他位置，并累加起来 tmp[j] = min(tmp[j+1], a[j]); res += tmp[j]; } for(int j = i+1; j <= n; j++) { tmp[j] = min(tmp[j-1],a[j]); res += tmp[j]; } if(res > ma) { /// 若比最大值大，更新答案 ma = res; ma_pos = i; } } ans[ma_pos] = a[ma_pos]; /// 根据取得最大值的位置，求出答案数组。 for(int i = ma_pos-1; i >= 1; i--) { ans[i] = min(ans[i+1], a[i]); } for(int i = ma_pos + 1; i <= n; i++) { ans[i] = min(ans[i-1], a[i]); } for(int i = 1; i <= n; i++) printf("%d ", ans[i]); return 0; }
这个时候，不能再 O(n^2) 暴力求解了，我们可以假设 pre[i] 为当前 a[i] = m[i] 且数组 a 在区间 [1,i] 非递减的最大总楼层数，然后再设 suc[i] 为当前 a[i] = m[i] 且数组 a 在区间 [i,n] 非递增的最大总楼层数，那么以 i 作为最高点能建的最大总楼层数为 pre[i] + suc[i] - m[i]。那么如果我们可以先预处理出 pre[i] 和 suc[i]，我们就只需 O(n) 的枚举最高点，维护一个 pre[i] + suc[i] - m[i] 的最大值以及取这个最大的位置 pos，最终根据这个 pos 去生成数组 a 即可。
那么 pre[i] 和 suc[i] 要怎么预处理呢。
对于 pre[i]，因为此时 a[i]=m[i]，那么如果 m[i-1] >= a[i]，a[i-1] 最多也只能取 a[i]，但是如果 a[i-1] <= m[i]，那么 a[i-1] 可以取到 m[i-1]，那既然 a[i-1] 可以取到 m[i-1] 了，对于区间 [1,i-1] 我们可以直接继承 pre[i-1] 就行了，因为我们要求 pre[i]，我们的 pre[1],pre[2]....pre[i] 肯定都是已经算好了。所以，对于 pre[i] 我们只需找到区间 [1,i-1] 中最后一个小于等于 m[i] 的位置 pos，那么 pre[i] = pre[pos] + (i-pos)*m[i]。
此时还有一个问题就是，怎么快速找到区间 [1,i-1] 中最后一个小于等于 m[i] 的位置 pos 呢，这个问题，可以用单调栈来求得。
对于 suc[i]，也是同样的道理，这次我们先求 suc[n]，再求 suc[n-1]，那么对于 suc[i] 我们找到区间 [i+1,n] 中第一个小于等于 m[i] 的位置 pos，那么 suc[i] = suc[pos] + (pos-i)*m[i]，依然用单调栈来找区间 [i+1,n] 中第一个小于等于 m[i] 的位置 pos。
那么总的复杂度是 O(n) 的。
#include <bits/stdc++.h> #define LL long long #define mem(i, j) memset(i, j, sizeof(i)) #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define pb push_back #define make make_pair #define INF INT_MAX #define inf LLONG_MAX #define PI acos(-1) using namespace std; const int N = 1e6 + 5; int a[N], pre[N], suc[N], s[N], tot, ans[N]; /// 这里的 pre[i] 是区间 [1,i-1] 中最后一个小于等于 a[i] 的位置，pre_sum[i] 才是它的总楼层，suc[i] 同理。 LL pre_sum[N], suc_sum[N]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); /// 预处理出 pre[i], pre_sum[i] for(int i = 1; i <= n; i++) { while(tot && a[i] < a[s[tot]]) tot--; pre[i] = s[tot]; pre_sum[i] = pre_sum[s[tot]] + 1LL * (i - s[tot]) * a[i]; s[++tot] = i; } /// 预处理出 suc[i], suc_sum[i] tot = 0; s[0] = n + 1; for(int i = n; i >= 1; i--) { while(tot && a[i] < a[s[tot]]) tot--; suc[i] = s[tot]; suc_sum[i] = suc_sum[s[tot]] + 1LL * (s[tot] - i) * a[i]; s[++tot] = i; } LL ma = 0LL; int pos = -1; /// 定义一个最大值，和取得最大值的位置 for(int i = 1; i <= n; i++) { if(pre_sum[i] + suc_sum[i] - 1LL * a[i] > ma) { ///维护最大值 ma = pre_sum[i] + suc_sum[i] - 1LL * a[i]; pos = i; } } for(int i = pos; i; i = pre[i]) { /// 求出答案数组 rep(j, pre[i] + 1, i) ans[j] = a[i]; } for(int i = pos; i <= n ; i = suc[i]) { rep(j, i, suc[i] - 1) ans[j] = a[i]; } for(int i = 1; i <= n; i++) printf("%d ", ans[i]); return 0; }
原文：https://www.cnblogs.com/Willems/p/14774104.html
