典型的动态规划，时间复杂度O(m*k)

解题思路:

注意事项:

参考代码:

#include

using namespace std;

#define maxn 100000000

#define maxm 1010

#define maxk 1010

#define maxB 1000010

#define maxC 1000010

#define maxv 1000010

#define inf INT_MAX

typedef long long ll;

ll n,m,k,v;

ll A[maxm],B[maxm],C[maxm];

ll dp[maxm][maxk];//dp[i][j]表示走完第i个红绿灯， 

//瞬移装置还需冷却j个红绿灯，这种情况下的最小用时 

//显然0<=i<=m,0<=j<=k-1 

ll waittime(ll t,int x){//在第x个路口等待，等待开始的时间为t，返回等待的时间长度 

int ret;

ret=t%(B[x]+C[x]);

if(ret<B[x])return 0;

else return B[x]+C[x]-ret;

}

int main(){

scanf("%lld%lld%lld%lld",&n,&m,&k,&v);

for(ll i=1;i<=m;i++){

scanf("%lld%lld%lld",&A[i],&B[i],&C[i]);

}

dp[0][0]=0;

for(int i=1;i<=k-1;i++){

dp[0][i]=inf;

}

for(ll i=1;i<=m;i++){

dp[i][0]=min(dp[i-1][0]+(A[i]-A[i-1])*v+waittime(dp[i-1][0]+(A[i]-A[i-1])*v,i),//可以开但不开瞬移 

             dp[i-1][1]+(A[i]-A[i-1])*v+waittime(dp[i-1][1]+(A[i]-A[i-1])*v,i));//开不了瞬移 

for(ll j=1;j<=k-2;j++){//开不了瞬移 

dp[i][j]=dp[i-1][j+1]+(A[i]-A[i-1])*v+waittime(dp[i-1][j+1]+(A[i]-A[i-1])*v,i);

}

dp[i][k-1]=dp[i-1][0]+waittime(dp[i-1][0],i);//开瞬移 

}

ll mintime=dp[m][0]+0;//直接瞬移到公司

for(ll i=1;i<=k-1;i++){

mintime=min(mintime,dp[m][i]+(n-A[m])*v);//走完最后一个路口还有n-A[m]的路程，并不是就结束了。

}

printf("%lld",mintime);

return 0;

}