题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
设方程 经过的i条路中已经跳过了j次的最短用时
dist[i - 1]是否跳过
跳过: dp[i][j] = dp[i - 1][j - 1] + dist[i - 1] / speed
不跳过: dp[i][j] = ceil(dp[i - 1][j] + dist[i - 1] / speed)
向上取整是因为对于最后一段dist[i - 1] / speed不需要跳过
C++ 代码
class Solution {
public int minSkips(int[] dist, int speed, int hoursBefore) {
int n = dist.length;
double INF = 1e9;
double EPS = 1e-8;
double[][] dp = new double[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
Arrays.fill(dp[i], INF);
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = Math.ceil(dp[i - 1][0] + (double)dist[i - 1] / speed);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (i == n) {
dp[i][j] = dp[i - 1][j] + (double)dist[i - 1] / speed;
} else {
dp[i][j] = Math.min(Math.ceil(dp[i - 1][j] + (double)dist[i - 1] / speed - EPS), dp[i - 1][j - 1] + (double)dist[i - 1] / speed);
}
}
}
int ans = -1;
for (int i = 0; i <= n; i++) {
if (dp[n][i] <= hoursBefore) {
ans = i;
break;
}
}
return ans;
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla