题目链接：点击打开链接
车可以减速！
车可以减速！
车可以减速！
重要的事情说三遍！一直在想车可不可以减速想了贼久Orz
首先，当某一个方向的车在行驶的时候，除非道路已经空了，否则另一个方向的车是不会走的。
于是方案就可以这么设计：A方向连续走过一些车——>B方向连续走过一些车——>A方向连续走过一些车——>B方向连续走过一些车——>。。。。。。
确定了分段走的思想之后，就可以确定如下dp形式：
设dp[i][j][k]为，A方向走掉了i辆车，B方向走过j辆车，最后走过的车是A方向的（k=0时）或者B方向的（k=1时）的情况下的最少花费时间
那么只要枚举所有可能的最后的A分段orB分段即可。
具体的计算方法的话，举个例子，
假设现在在计算dp[i][j][0]，枚举到dp[i][l][1]，那么在这个枚举下要计算的就是在dp[i][l][1]这个时间点开始，A方向从第l+1辆到第j辆连续通过道路的最早完成时间点。
直接递推计算即可其实。设上一辆车的出发时间为s，到达时间为t，并且设下一辆车的到达出发点的时间为ti，走这条路所需的最短时间为di，那么下一辆车的最早出发时间就是S=max(s+10,ti)，最早到达时间就是T=max(t+10,S+di)，+10是因为每两辆车之间要隔10秒的路程。由于车是可以减速的所以这样的递推成立。
代码如下：
#include<bits/stdc++.h> using namespace std; struct node { int t,d; node(int tt=0,int dd=0):t(tt),d(dd){} }; node a[205],b[205]; int atop,btop; int dp[205][205][2]; int main() { int t; scanf("%d",&t); while(t--) { atop=btop=1; int n; scanf("%d",&n); for(int i=0;i<n;i++) { char s[5]; scanf("%s",s); if(s[0]=='A') { scanf("%d%d",&a[atop].t,&a[atop].d); atop++; } else { scanf("%d%d",&b[btop].t,&b[btop].d); btop++; } } for(int i=0;i<atop;i++) for(int j=0;j<btop;j++) dp[i][j][0]=dp[i][j][1]=10000000; dp[0][0][0]=dp[0][0][1]=0; for(int i=0;i<atop;i++) for(int j=0;j<btop;j++) { // printf("dp[%d][%d][%d]=%d\ndp[%d][%d][%d]=%d\n\n",i,j,0,dp[i][j][0],i,j,1,dp[i][j][1]); node p=node(dp[i][j][1]-10,dp[i][j][1]-10); for(int k=i+1;k<atop;k++) { node pp; pp.t=max(p.t+10,a[k].t); pp.d=max(p.d+10,pp.t+a[k].d); p=pp; dp[k][j][0]=min(dp[k][j][0],p.d); } p=node(dp[i][j][0]-10,dp[i][j][0]-10); for(int k=j+1;k<btop;k++) { node pp; pp.t=max(p.t+10,b[k].t); pp.d=max(p.d+10,pp.t+b[k].d); p=pp; dp[i][k][1]=min(dp[i][k][1],p.d); } } int ans=min(dp[atop-1][btop-1][0],dp[atop-1][btop-1][1]); printf("%d\n",ans); } }