题意:
给定一排 n 个点,每个点有 \(h_i\) 和 \(v_i\)。把它们划分成任意数量的连续段,每个点仅属于一段,每段的价值等于段中 \(h\) 最小的点的 \(v\) 值。求最大价值和
\(h_i\) 为 1~n 的一个排列,\(-1e9\le v_i\le 1e9\)
思路:
用到单调(递增)栈的两个性质:1. 栈顶是左边小于 \(a_i\) 的最近位置;2. 对原数组的每个位置 \(j\)(不一定在单调栈里),\(j\) 右边最近的在单调栈里的位置 \(stk_t\) 就是 \([j,i]\) 中 \(a\) 最小的位置。
\(f_i\) 表示处理到 \(i\) 的最大价值。按 \(h_i\) 维护单调栈。有两种更新方式:
对于 2,\(stk_{top}\) 之前的信息已经在 \(f[stk]\) 中,要算的是新的一段即 \([stk_{top}+1,i-1]\) 中最大的 \(f\)。开个数组 \(mf[i]\) 记录一下处理到 \(i\) 时,弹出的所有 \(f\) 的最大值,包括 \(f_i\)
哎讲不清楚,这玩意太难描述了,摆了
ll n, h[N], v[N], f[N], mf[N]; //弹掉的东西的最大f值,包括自己 int stk[N], top; void sol() { cin >> n; for(int i = 1; i <= n; i++) cin >> h[i]; for(int i = 1; i <= n; i++) cin >> v[i]; memset(mf, -INF, sizeof mf); //初始化 for(int i = 1; i <= n; i++) { mf[i] = f[stk[top]]; while(h[stk[top]] > h[i]) mf[i] = max(mf[i], mf[stk[top--]]); f[i] = max({top ? f[stk[top]] : v[i], mf[i] + v[i]}); stk[++top] = i; mf[i] = max(mf[i], f[i]); } cout << f[n]; }