Description

Submission

class Solution {
    const double eps = 1e-8;
public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        dist.insert(dist.begin(), 0);

        vector<vector<double>> dp(n+1, vector<double>(n+1, 1e20));
        dp[0][0] = 0;

        for(int i = 1; i < n; ++i) {
            for(int j = 0; j <= i; ++j) {
                dp[i][j] = ceil(dp[i-1][j] + double(dist[i]) / speed - eps);
                if(j >= 1) {
                    dp[i][j] = min(dp[i-1][j-1] + double(dist[i]) / speed, dp[i][j]);
                }   
            }
        }


        for(int j = 0; j <= n; ++j) {
            dp[n][j] = dp[n-1][j] + double(dist[n]) / speed;
            if(dp[n][j] <= hoursBefore) return j;
        }

        return -1;
    }
};

// dp[n][k]: minimum hours needed to arrive at the n-th road with k skips