解题思路
这是一道动态规划问题，主要思路如下：
-
问题分析：
- 给定
个位置的墙壁高度
- 可以增加总共
个单位的高度
- 需要找到最优的扩容方案
- 给定
-
解决方案：
- 计算左右两侧的单调递增序列
- 计算每个区间的剩余空间
- 动态规划处理高度分配
-
关键步骤：
- 维护前缀和数组
- 计算每个区间的最大容量
- 考虑不同分配方案的组合
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 计算从左到右的单调递增序列
vector<int> calLeft(int n, vector<int>& h) {
vector<int> next;
next.push_back(0);
for (int i = 1; i < n; i++) {
if (h[i] > h[next.back()])
next.push_back(i);
}
return next;
}
// 计算从右到左的单调递增序列
vector<int> calRight(int n, vector<int>& h) {
vector<int> next;
next.push_back(n-1);
for (int i = n-2; i >= 0; i--) {
if (h[i] > h[next.back()])
next.push_back(i);
}
return next;
}
// 计算区间剩余空间
vector<int> calRemain(vector<int>& next, vector<int>& h) {
int r = 0;
vector<int> remain(next.size());
for (int i = 1; i < remain.size(); i++) {
r = max(abs(next[i] - next[i-1]) - 1, r);
remain[i] = r;
}
return remain;
}
// 计算最大容量
vector<int> calMaxV(vector<int>& next, int m, vector<int>& sum,
vector<int>& h, vector<int>& zero) {
vector<int> maxP(m+1);
for (int i = 0; i < next.size()-1; i++) {
zero[i] = maxP[0];
int temp = maxP[0], temp1 = m > 1 ? maxP[1] : 0;
int rightI = i + 1;
for (int j = 0; j <= m; j++) {
maxP[j] = max(maxP[j], j > 0 ? maxP[j-1] : 0);
while (rightI < next.size() && h[next[i]] + j > h[next[rightI]])
rightI++;
int width = abs(next[min(rightI, (int)next.size()-1)] - next[i]) - 1;
int height = min(h[next[i]] + j, h[next.back()]);
int build = abs(sum[next[min(rightI, (int)next.size()-1)] -
(next[0] < next[1])] - sum[next[i] - (next[0] > next[1])]);
int pre = rightI == next.size() ? temp1 : temp;
maxP[j] = max(width * height - build + pre, maxP[j]);
}
}
zero[zero.size()-1] = maxP[0];
return maxP;
}
int main() {
int n, m, s = 0, maxI = 0;
cin >> n;
vector<int> h(n), sum(n), rsum(n);
// 读入数据并计算前缀和
for (int i = 0; i < n; i++) {
cin >> h[i];
s += h[i];
sum[i] = s;
if (h[i] > h[maxI])
maxI = i;
}
// 计算后缀和
s = 0;
for (int i = n-1; i >= 0; i--) {
s += h[i];
rsum[n-i-1] = s;
}
cin >> m;
// 计算左右边界和最大容量
vector<int> left = calLeft(n, h);
vector<int> right = calRight(n, h);
vector<int> leftZero(left.size()), rightZero(right.size());
vector<int> reLeft = calRemain(left, h);
vector<int> reRight = calRemain(right, h);
vector<int> maxL = calMaxV(left, m, sum, h, leftZero);
vector<int> maxR = calMaxV(right, m, sum, h, rightZero);
// 计算最终结果
int ans = 0;
for (int i = 0; i <= m; i++) {
ans = max(ans, maxL[i] + maxR[m-i]);
}
// 处理特殊情况
if (right.back() != left.back())
ans += (right.back() - left.back() - 1) * h[left.back()] -
sum[right.back() - 1] + sum[left.back()];
// 考虑所有可能的组合
for (int i = 0; i < left.size(); i++) {
for (int j = 0; j < right.size() && right[j] > left[i]; j++) {
int width = right[j] - left[i] - 1;
int height = (h[right[j]] + h[left[i]] + m) / 2;
if (height <= h[left.back()])
continue;
int build = sum[right[j]-1] - sum[left[i]];
int pre = (h[right[j]] + h[left[i]] + m) % 2 == 0 ?
0 : max(reRight[j], reLeft[i]);
ans = max(width * height - build + pre + leftZero[i] + rightZero[j], ans);
}
}
cout << ans;
return 0;
}
import java.util.*;
public class Main {
// 计算从左到右的单调递增序列
private static List<Integer> calLeft(int n, int[] h) {
List<Integer> next = new ArrayList<>();
next.add(0);
for (int i = 1; i < n; i++) {
if (h[i] > h[next.get(next.size()-1)]) {
next.add(i);
}
}
return next;
}
// 计算从右到左的单调递增序列
private static List<Integer> calRight(int n, int[] h) {
List<Integer> next = new ArrayList<>();
next.add(n-1);
for (int i = n-2; i >= 0; i--) {
if (h[i] > h[next.get(next.size()-1)]) {
next.add(i);
}
}
return next;
}
// 计算区间剩余空间
private static int[] calRemain(List<Integer> next, int[] h) {
int r = 0;
int[] remain = new int[next.size()];
for (int i = 1; i < remain.length; i++) {
r = Math.max(Math.abs(next.get(i) - next.get(i-1)) - 1, r);
remain[i] = r;
}
return remain;
}
// 计算最大容量
private static int[] calMaxV(List<Integer> next, int m, int[] sum,
int[] h, int[] zero) {
int[] maxP = new int[m+1];
for (int i = 0; i < next.size()-1; i++) {
zero[i] = maxP[0];
int temp = maxP[0], temp1 = m > 1 ? maxP[1] : 0;
int rightI = i + 1;
for (int j = 0; j <= m; j++) {
maxP[j] = Math.max(maxP[j], j > 0 ? maxP[j-1] : 0);
while (rightI < next.size() &&
h[next.get(i)] + j > h[next.get(rightI)]) {
rightI++;
}
int width = Math.abs(next.get(Math.min(rightI, next.size()-1)) -
next.get(i)) - 1;
int height = Math.min(h[next.get(i)] + j, h[next.get(next.size()-1)]);
int build = Math.abs(sum[next.get(Math.min(rightI, next.size()-1)) -
(next.get(0) < next.get(1) ? 1 : 0)] -
sum[next.get(i) - (next.get(0) > next.get(1) ? 1 : 0)]);
int pre = rightI == next.size() ? temp1 : temp;
maxP[j] = Math.max(width * height - build + pre, maxP[j]);
}
}
zero[zero.length-1] = maxP[0];
return maxP;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] h = new int[n];
int[] sum = new int[n];
int[] rsum = new int[n];
// 读入数据并计算前缀和
int s = 0, maxI = 0;
for (int i = 0; i < n; i++) {
h[i] = sc.nextInt();
s += h[i];
sum[i] = s;
if (h[i] > h[maxI]) {
maxI = i;
}
}
// 计算后缀和
s = 0;
for (int i = n-1; i >= 0; i--) {
s += h[i];
rsum[n-i-1] = s;
}
int m = sc.nextInt();
// 计算左右边界和最大容量
List<Integer> left = calLeft(n, h);
List<Integer> right = calRight(n, h);
int[] leftZero = new int[left.size()];
int[] rightZero = new int[right.size()];
int[] reLeft = calRemain(left, h);
int[] reRight = calRemain(right, h);
int[] maxL = calMaxV(left, m, sum, h, leftZero);
int[] maxR = calMaxV(right, m, sum, h, rightZero);
// 计算最终结果
int ans = 0;
for (int i = 0; i <= m; i++) {
ans = Math.max(ans, maxL[i] + maxR[m-i]);
}
// 处理特殊情况
if (right.get(right.size()-1) != left.get(left.size()-1)) {
ans += (right.get(right.size()-1) - left.get(left.size()-1) - 1) *
h[left.get(left.size()-1)] - sum[right.get(right.size()-1) - 1] +
sum[left.get(left.size()-1)];
}
// 考虑所有可能的组合
for (int i = 0; i < left.size(); i++) {
for (int j = 0; j < right.size() && right.get(j) > left.get(i); j++) {
int width = right.get(j) - left.get(i) - 1;
int height = (h[right.get(j)] + h[left.get(i)] + m) / 2;
if (height <= h[left.get(left.size()-1)]) {
continue;
}
int build = sum[right.get(j)-1] - sum[left.get(i)];
int pre = (h[right.get(j)] + h[left.get(i)] + m) % 2 == 0 ?
0 : Math.max(reRight[j], reLeft[i]);
ans = Math.max(width * height - build + pre + leftZero[i] +
rightZero[j], ans);
}
}
System.out.println(ans);
}
}
def cal_left(n, h):
next = [0]
for i in range(1, n):
if h[i] > h[next[-1]]:
next.append(i)
return next
def cal_right(n, h):
next = [n-1]
for i in range(n-2, -1, -1):
if h[i] > h[next[-1]]:
next.append(i)
return next
def cal_remain(next, h):
r = 0
remain = [0] * len(next)
for i in range(1, len(remain)):
r = max(abs(next[i] - next[i-1]) - 1, r)
remain[i] = r
return remain
def cal_max_v(next, m, sum_arr, h, zero):
max_p = [0] * (m+1)
for i in range(len(next)-1):
zero[i] = max_p[0]
temp = max_p[0]
temp1 = max_p[1] if m > 1 else 0
right_i = i + 1
for j in range(m+1):
max_p[j] = max(max_p[j], max_p[j-1] if j > 0 else 0)
while right_i < len(next) and h[next[i]] + j > h[next[right_i]]:
right_i += 1
width = abs(next[min(right_i, len(next)-1)] - next[i]) - 1
height = min(h[next[i]] + j, h[next[-1]])
build = abs(sum_arr[next[min(right_i, len(next)-1)] -
(next[0] < next[1])] - sum_arr[next[i] - (next[0] > next[1])])
pre = temp1 if right_i == len(next) else temp
max_p[j] = max(width * height - build + pre, max_p[j])
zero[-1] = max_p[0]
return max_p
def main():
n = int(input())
h = [int(input()) for _ in range(n)]
m = int(input())
# 计算前缀和和后缀和
sum_arr = [0] * n
rsum = [0] * n
s = 0
max_i = 0
for i in range(n):
s += h[i]
sum_arr[i] = s
if h[i] > h[max_i]:
max_i = i
s = 0
for i in range(n-1, -1, -1):
s += h[i]
rsum[n-i-1] = s
# 计算左右边界和最大容量
left = cal_left(n, h)
right = cal_right(n, h)
left_zero = [0] * len(left)
right_zero = [0] * len(right)
re_left = cal_remain(left, h)
re_right = cal_remain(right, h)
max_l = cal_max_v(left, m, sum_arr, h, left_zero)
max_r = cal_max_v(right, m, sum_arr, h, right_zero)
# 计算最终结果
ans = max(max_l[i] + max_r[m-i] for i in range(m+1))
if right[-1] != left[-1]:
ans += ((right[-1] - left[-1] - 1) * h[left[-1]] -
sum_arr[right[-1] - 1] + sum_arr[left[-1]])
# 考虑所有可能的组合
for i in range(len(left)):
for j in range(len(right)):
if right[j] <= left[i]:
continue
width = right[j] - left[i] - 1
height = (h[right[j]] + h[left[i]] + m) // 2
if height <= h[left[-1]]:
continue
build = sum_arr[right[j]-1] - sum_arr[left[i]]
pre = (0 if (h[right[j]] + h[left[i]] + m) % 2 == 0
else max(re_right[j], re_left[i]))
ans = max(width * height - build + pre + left_zero[i] + right_zero[j], ans)
print(ans)
if __name__ == "__main__":
main()
算法及复杂度
- 算法：动态规划 + 贪心
- 时间复杂度：
-
- 空间复杂度：
- 需要存储前缀和、后缀和和动态规划数组
京公网安备 11010502036488号