P1003（C语言）

解题思路:

动态规划的思想，这里优化了一下，没有使用dp数组，降低空间复杂度，用两个int变量表示。

从起点到当前路段并返回的总时间 = 上一段路往返总耗时 + 当前路段往返耗时(dp[i] = dp[i-1] + dp[i])

注意事项:

参考代码:

#include <stdio.h>

int getReturn(int u, int f, int d, char ch) {
    if (ch == 'f') {
        return f * 2;       // 平地
    } else {
        return u + d;       // 上下坡
    }
}

int main() {
    int M, T, U, F, D;
    scanf("%d %d %d %d %d", &M, &T, &U, &F, &D);
    int reach = 0;      // 最终达到的路段数
    int pre = 0, cur;       // 前一段路耗时总耗时，当前路段耗时
    char road;      // 当前路段的情况（上坡、平底、下坡）
    for (int i = 0; i < T; i++) {
        getchar();      // 吸收上一行的换行符\n
        scanf("%c", &road);
        int t = getReturn(U, F, D, road);       // 第i段路往返所需时间
        cur = i == 0 ? t : pre + t;       // 当前路段总耗时 = 前面路段总耗时 + 当前路段往返耗时
        pre = cur;      // 对于下一段路来说，更新它的前面路段总耗时
        if (cur <= M) {
            reach++;
        }
    }
    printf("%d", reach);
    return 0;
}