问题描述

爱丽丝要开车去上班, 上班的路上有许多红绿灯, 这让爱丽丝很难过。为 了上班不迟到, 她给自己的车安装了氮气喷射装置。现在她想知道自己上班最 短需要多少时间。

爱丽丝的车最高速度是  米每秒, 并且经过改装后, 可以瞬间加速到小于 等于最高速的任意速度, 也可以瞵间停止。

爱丽丝家离公司有 N 米远, 路上有 M 个红绿灯, 第 i 个红绿灯位于离爱 丽丝家 Ai​ 米远的位置, 绿灯持续 Bi​ 秒, 红灯持续 Ci​ 秒。在初始时 (爱丽丝开始计时的瞬间), 所有红绿灯都恰好从红灯变为绿灯。如果爱丽丝在绿灯变红时刚好到达红绿灯, 她会停下车等红灯, 因为她是遵纪守法的好市民。

氮气喷射装置可以让爱丽丝的车瞬间加速到超光速 (且不受相对论效应的影响!), 达到瞬移的效果, 但是爱丽丝是遵纪守法的好市民, 在每个红绿灯前她都会停下氮气喷射, 即使是绿灯, 因为红绿灯处有斑马线, 而使用氮气喷射 装置通过斑马线是违法的。此外, 氮气喷射装置不能连续启动, 需要一定时间 的冷却, 表现为通过 K 个红绿灯后才能再次使用。(也就是说, 如果 K=1, 就 能一直使用啦!) 初始时, 氮气喷射装置处于可用状态。

输入格式

第一行四个正整数 N、M、K、V, 含义如题面所述。

接下来 M 行, 每行三个正整数 Ai 、 Bi 、 Ci，含义如题面所述。

输出格式

输出一个正整数 T, 表示爱丽丝到达公司最短需要多少秒。

样例输入

90 2 2 2
30 20 20 
60 20 20

样例输出

80

样例说明

爱丽丝在最开始直接使用氮气喷射装置瞬间到达第一个红绿灯, 然后绿灯通过, 以最高速行进 60 秒后到达第二个红绿灯, 此时绿灯刚好变红, 于是她等 待 20 秒再次变为绿灯后通过该红绿灯, 此时氮气喷射装置冷却完毕, 爱丽丝再 次使用瞬间到达公司, 总共用时 80 秒。

评测用例规模与约定

对于 30% 的数据, N < 100 ; M < 10 ; M < K ; V = 1.

对于 60% 的数据, N ≤ 1000; M ≤ 100; K ≤ 50; Bi​,Ci ​≤ 100; V ≤ 10.

对于 100% 的数据, 0 < N ≤ 10^8; M ≤ 1000; K ≤ 1000; 0 < Bi​,Ci ​≤ 10^6; V ≤ 10^6; 0 < Ai ​< N; 对任意 i < j, 有 Ai​ < Aj​.

解题思路

动态规划方程

这是一道比较明显的动态规划，对于到达第 i 个路口，可以考虑开车过来还是闪现过来。

如果是开车过来，那么dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + s + t

如果是闪现过来，那么意味着前k个路口必须都是开车过来的，从i-1路口闪现过来

那么dp[i][1] = min(dp[i - k][0], dp[i - k][1]) + S + t

处理细节

接下来就是一些细节，比如说如何计算t，如何计算大S。

根据具体代码中calc方法中的算式，当前时间对红绿灯组合时间取余，可以得到当前时间在一个红绿灯周期中的位置，如果超过了绿灯时间，就要等红灯，进行简单计算即可。

对于大S，我们先取到达i - k节点最短的时间，并从i - k节点开始开始往后加，只要利用calc方法正常循环增加每一条路和红绿灯的时间，就可以得到到达i节点的时间，由于i - 1到i节点是闪现过来的，所以这段距离特殊处理为0即可。

另外，由于从最后一个路口到公司也可以使用氮气喷射，所以我们将公司节点额外添加并特殊处理红路灯时间即可，笔者定义绿灯时间为1，红灯时间为0，可以达到不用等红绿灯的效果。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        // 额外添加一个特殊的公司节点
        int m = sc.nextInt() + 1;
        int k = sc.nextInt();
        long v = sc.nextInt();
        long[] a = new long[m + 1], b = new long[m + 1], c = new long[m + 1];
        for (int i = 1; i <= m - 1; i++) {
            // 将所有距离乘v就可以当做单位1来计算
            a[i] = sc.nextInt() * v;
            b[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }
        // 为公司定义一个特殊的红绿灯时间
        a[m] = n * v; b[m] = 1; c[m] = 0;

        // 以下dp状态均表示等完i路口红绿灯后的时间
        // dp[i][0] 表示从i-1号节点开车过来
        // dp[i][1] 表示从i-1号节点闪现过来
        long[][] dp = new long[m + 1][2];
        for (int i = 1; i <= m; i++) {
            long s1 = a[i] - a[i - 1];
            long time1 = calc(dp[i - 1][0], s1, b[i], c[i]);
            long time2 = calc(dp[i - 1][1], s1, b[i], c[i]);
            // 从到达i-1节点的最短时间直接开车过来
            dp[i][0] = Math.min(time1, time2);

            // 从i-1节点闪现过来，要从i-k节点一直开车过来
            int po = Math.max(0, i - k);
            // 在位置po选一个最短的做起始时间time3
            long time3 = Math.min(dp[po][0], dp[po][1]);
            // 起点区间：[po, i-1]
            for (int j = po; j <= i - 1; j++) {
                long s = a[j + 1] - a[j];
                // 如果是i-1号路口，表示闪现，距离设置为0
                if (j == i - 1) {
                    s = 0;
                }
                time3 = calc(time3, s, b[j + 1], c[j + 1]);
            }
            dp[i][1] = time3;
        }
        System.out.print(Math.min(dp[m][0], dp[m][1]));
    }
    // 起始时间start，返回到达下一个路口等完红绿灯的时间
    public static long calc(long start, long s, long green, long red) {
        // res 初始化为到达路口的时间
        long res = start + s;
        long t = (start + s) % (green + red);
        // 根据消除多轮红绿灯组合的剩余时间，计算等红灯时间
        if (t >= green) {
            res += (green + red) - t;
        }
        return res;
    }
}