题意：
有一个单行道，两个方向都有车在等待。给出每个车的方向以及到达的时间以及走完这段路所需要的时间。
为了防止车祸，同向两车通过任一点的时间间隔不得小于10s。
求最后一辆车离开时刻的最小值。
思路：
这题最坑的就是，车可以降低速度。provided it is not slowed down by other cars in front。
分析一下样例2，
4
A 0 100
B 50 100
A 100 1
A 170 100
首先B走，到达时间为150s，之后A1走，到达时间为250s，然后在160s的时候，A2可以出发，可以降低到和A1一直相隔10s的速度，到达时间为260s，也比A1晚10s。
之后A3在170s出发，270s到达，所以花费的总时间是270s。
不难想到的是，整个过程是A先走若干个 -> B走若干个 -> A走若干个。。。。。知道走完。
所以设dp[i][j][0/1]表示走了i辆A，j辆B且A是最后一辆（0），B是最后一辆（1）所花费的最少时间。
根据上面的过程，在dp[i][j][0]的时候，就可以枚举B走了K辆；
在dp[i][j][1]的时候，枚举A走了K辆。
由于同向的车每次相隔必须大于等于10s，所以设前一辆同向的车的出发时间为x，到达时间为y，本辆车实际到达的时间为a，那么出发时间就是b = max(a,x + 10)，到达时间就是max(b,y + 10)。
时间复杂度为n^3。数据应该略水。。。。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = ;
ll dp[N][N][];
struct node
{
ll arr,cost;
node(){};
node(int x,int y):arr(x),cost(y){};
}a[N],b[N];
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int orz;
int n = ,m = ;
scanf("%d",&orz);
for (int i = ;i < orz;i++)
{
char s[];
int x,y;
scanf("%s%d%d",s,&x,&y);
if (s[] == 'A') a[++n] = node(x,y);
else b[++m] = node(x,y);
}
for (int i = ;i <= n;i++)
{
for (int j = ;j <= m;j++) dp[i][j][] = dp[i][j][] = 1e16;
}
dp[][][] = dp[][][] = ;
for (int i = ;i <= n;i++)
{
for (int j = ;j <= m;j++)
{
ll t1 = dp[i][j][],t2 = ;
for (int k = j + ;k <= m;k++)
{
t1 = max(t1,b[k].arr);
t2 = max(t2,t1 + b[k].cost);
dp[i][k][] = min(dp[i][k][],t2);
t1 += ;
t2 += ;
}
t1 = dp[i][j][],t2 = ;
for (int k = i + ;k <= n;k++)
{
t1 = max(t1,a[k].arr);
t2 = max(t2,t1 + a[k].cost);
dp[k][j][] = min(dp[k][j][],t2);
t1 += ;
t2 += ;
}
}
}
printf("%lld\n",min(dp[n][m][],dp[n][m][]));
}
return ;
}
/*
2
4
A 0 60
B 19 10
B 80 20
A 85 100
4
A 0 100
B 50 100
A 100 1
A 170 100
*/