超级码力在线编程大赛初赛 第1场 3.大楼间穿梭 单调栈,DP
题意
一座城市有(n) 座高楼在城市的水平线上,楼高(h[i]) 。蜘蛛侠要从第一座楼开始到第(n) 座楼,蜘蛛侠有两种选择
- 花费(x) ,选择跳到第(i+1) 或者第(i+2) 座楼
- 花费(y) ,选择跳到接下来的(k) 座楼中,第一个不小于当前楼的楼
问最小的花费
分析
很明显是简单的决策型(dp) ,(dp[i]) 表示从第(i)座楼开始跳到第(n) 座楼的最小花费,很容易写出转移方程
[dp[i] = min(min(dp[i+1],dp[i+2])+x),dp[pos]+y)
]
所以问题变成了怎么快速计算出(pos) ,相当于快速计算出数组中第一个比当前大的位置,很明显可以用单调栈的性质预处理出(next) 数组,具体只需维护一个单调递减的单调栈。
(dp) 过程可以用记忆化搜索实现,提交了一直(wa) ,后来发现初始化(dp) 数组不能用(0)
代码
ll dp[100005];
int nxt[100005];
class Solution {
public:
void init(vector<int>& h) {
stack<int> st;
for (int i = 0; i < h.size(); i++) nxt[i] = 1e8 + 5, dp[i] = 1e16;
for (int i = 0; i < h.size(); i++) {
while (!st.empty() && h[i] >= h[st.top()]) {
nxt[st.top()] = i;
st.pop();
}
st.push(i);
}
}
ll dfs(int cur, int k, int x, int y, vector<int>& h) {
if (cur == h.size() - 1) return 0;
else if (cur >= h.size()) return 1e18;
if (dp[cur] != 1e16) return dp[cur];
ll res1 = min(dfs(cur + 1, k, x, y, h), dfs(cur + 2, k, x, y, h)) + y;
ll res2 = 1e16;
int pos = nxt[cur];
if (pos - cur <= k && pos <= h.size() - 1) res2 = dfs(pos, k, x, y, h) + x;
return dp[cur] = min(res1, res2);
}
long long shuttleInBuildings(vector<int>& heights, int k, int x, int y) {
init(heights);
return dfs(0, k, x, y, heights);
}
};