Problem E
Mountain Road
In the Franconian Switzerland, there is a narrow mountain road. With only a single lane, this is a bottleneck for two-way traffic. Your job is to schedule incoming cars at both ends so that the last car leaves the road as early as possible.
Each car is specified by three values: the direction in which it is going, the arrival time at the corresponding beginning of the road, and the driving time this car needs to get through, provided it is not slowed down by other cars in front. Cars cannot overtake each other on the mountain road, and reordering cars in the queues at the ends of the road is not allowed.
For safety reasons, two successive cars going in the same direction may not pass any point of the road within less than 10 seconds. This ensures that the second car will not crash into the first car if the latter brakes hard. However, if another car passes in the other direction in between, it will be clear that the road is empty, so in this case, this rule does not apply.
Input
The first line of the input consists of a single integer c (1 ≤ c ≤ 200), the number of test cases.
Then follow the test cases, each beginning with a single line consisting of an integer n (1 ≤ n ≤ 200), the number of cars you are to consider in this test case. The remainder of each test case consists of nlines, one line per car, starting with a single upper case letter (“A” or “B”), giving the direction in which the car is going. Then follow, on the same line, two integers t (0 ≤ t ≤ 100000) and d (1 ≤ d ≤100000), giving the arrival time at the beginning of the road and the minimum travel time, respectively, both in seconds.
Within a test case, the cars are given in order of increasing arrival time, and no two cars will arrive at the same time.
Output
For each test case, print a single line consisting of the point in time (in seconds) the last car leaves the road when the cars are scheduled optimally.
題意：A，B兩點，給定n輛車，A，B為車的目的地，t為發車時間，d為最快的路程花費的時間。由於要確保安全，要滿足一下兩個條件：
1、不能有反方向的車
2、相同方向的車之間時間不能相差小於10秒。
問所有汽車最小需要的時間。
思路：先是貪心的思想，方向相同放在一起，發車時間小的肯定是先發最優。題目給定的已經是升序了，所以無需排序。
然後是DP，把A和B方向車分開存，dp[i][j][d]代表的是前i輛A車，j輛B車，最後一輛方向為d，需要的最少時間。方向A為0，B為1
這樣由dp[i][j][0]這個狀態可以往後選x輛B，dp[i][j][1]這個狀態可以往後選x輛A，起始時間為dp[i][j] dp[k][j](如果是B為dp[i][k]) = min{time};
time的求法為從起始時間開始確定，每次維護起始時間和到達時間即可，注意由於間隔要大於10，所以最後後面要+10.
代碼：
#include#include #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) #define INF 0x3f3f3f3f const int N = 205; int t, n, an, bn, dp[N][N][2]; struct Car { int s, t; } a[N], b[N]; int solve() { dp[0][0][0] = dp[0][0][1] = 0; for (int i = 0; i <= an; i++) { for (int j = 0; j <= bn; j++) { int s = dp[i][j][1], end = 0, k; for (k = i + 1; k <= an; k++) { s = max(s, a[k].s); end = max(s + a[k].t, end); dp[k][j][0] = min(dp[k][j][0], end); s += 10; end += 10; } s = dp[i][j][0]; end = 0; for (k = j + 1; k <= bn; k++) { s = max(s, b[k].s); end = max(s + b[k].t, end); dp[i][k][1] = min(dp[i][k][1], end); s += 10; end += 10; } } } return min(dp[an][bn][0], dp[an][bn][1]); } int main() { scanf("%d", &t); while (t--) { memset(dp, INF, sizeof(dp)); an = bn = 0; scanf("%d", &n); int S, T; char C[2]; while (n--) { scanf("%s%d%d", C, &S, &T); if (C[0] == 'A') { an++; a[an].s = S; a[an].t = T; } else { bn++; b[bn].s = S; b[bn].t = T; } } printf("%d\n", solve()); } return 0; }
