2020超级码力初赛-Round1-C

2020超级码力初赛-Round1-C

八月 29, 2020

大楼间穿梭

题意

蜘蛛侠在大楼间穿梭。大楼的高度可以看作是一个从左到右排列的数组。 现在蜘蛛侠站在第一栋大楼上，他想跳到最后一栋上。 蜘蛛侠的视野为 k，他可以花费 x 点体力，用蛛丝移动到右侧 k 幢建筑中第一栋比当前位置高的大楼。 或者蜘蛛侠可以花费 y 点体力，跳跃到右侧接下来两栋大楼其中一栋。 请计算蜘蛛侠最少花费多少体力，到达最后一栋上。

大楼的高度为数组 heights，一共有 n 栋大楼，2≤n≤105, 1≤$heights_i$≤109. 蜘蛛侠的视野为 k，1≤k≤n。 两种行动的体力花费满足 1≤x,y≤109。

题解

很显然题目已经说明了转移方程

难点在于对于第i个位置 如何快速得到k距离内能跳到的下一个大楼

朴素想法$On^2$ 暴力 。

发现“右边第一个比自己大的数字”是单调栈的经典模型

那么这个问题可以通过单调栈预处理对于位置i它能跳到最近的位置j满足$heights_j>heights_i$ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    /**
     * @param heights: the heights of buildings.
     * @param k: the vision.
     * @param x: the energy to spend of the first action.
     * @param y: the energy to spend of the second action.
     * @return: the minimal energy to spend.
     */
    int nextpos[(int)1e5+5];
    long long dp[(int)1e5+5];
    long long shuttleInBuildings(vector<int> &heights, int k, int x, int y) {
        int n=heights.size();
        stack<int>st;
        long long ans=0;int pos=0;
        for(int i=0;i<=n;i++)nextpos[i]=n+1,dp[i]=1e18;
        for(int i=0;i<n;i++){
            //if(i)dp[i]=1e18;
            while(!st.empty()&&heights[st.top()]<=heights[i]){
                nextpos[st.top()]=i;
                st.pop();
            }
            st.push(i);
        }
        dp[0]=0;
        for(int i=0;i<n;i++){
            if(i+1<n)dp[i+1]=min(dp[i+1],dp[i]+y);
            if(i+2<n)dp[i+2]=min(dp[i+2],dp[i]+y);
            if(nextpos[i]-i<=k)dp[nextpos[i]]=min(dp[nextpos[i]],dp[i]+x);
        }
        return dp[n-1];
    }
};