比赛的时候以为是贪心…
想了好久.
不过最后没敢写，因为没办法证明正确性，只是直觉==
最后剩下的时间给队友改另一道题了..
果然明智…
蠢的人的直觉真心不靠谱..
这题是dp
我们可以把车按照方向的不同分为A车和B车
dp[i][j][0..1]表示已经经过了a方向的i辆车，经过了b方向的j辆车，并且最后一辆车是a/b方向的情况的离开道路的时间.
似乎问题不大.
然后就一直wa…
wa到怀疑人生好么！!!
最后发现
问题出在!
dp数组初始化赋值成正无穷的时候，溢出啦!
然后我搜了下，发现0x7fffffff果然不是什么好东西!
以后正无穷用0x3f3f3f3f
这东西>1E9，相加不超过int
而且最重要的是，如果定义 inf = 0x3f3f3f3f
0x3f3f3f3f的每个字节都是0x3f！所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))
不要使用0x7fffffff!
不要使用0x7fffffff!
不要使用0x7fffffff!
代码实现
1/*************************************************************************
2 > File Name: code/2015summer/0821/E.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月21日 星期五 01时28分23秒
6 ************************************************************************/
7#include<iostream>
8#include<iomanip>
9#include<cstdio>
10#include<algorithm>
11#include<cmath>
12#include<cstring>
13#include<string>
14#include<map>
15#include<set>
16#include<queue>
17#include<vector>
18#include<stack>
19#define y0 abc111qqz
20#define y1 hust111qqz
21#define yn hez111qqz
22#define j1 cute111qqz
23#define tm crazy111qqz
24#define lr dying111qqz
25using namespace std;
26#define REP(i, n) for (int i=0;i<int(n);++i)
27typedef long long LL;
28typedef unsigned long long ULL;
29const int inf = 0x7fffffff;
30const int N=2E2+7;
31int dp[N][N][2];
32int cntA,cntB;
33struct Q{
34 int beg,t;
35 char dir;
36}q[N],a[N],b[N];
37void init(){
38 int n;
39 int beg,time;
40 char dir;
41 scanf("%d",&n);
42 cntA = 0 ;
43 cntB = 0 ;
44 for ( int i = 0 ; i < n ;i++){
45 cin>>q[i].dir>>q[i].beg>>q[i].t;
46 }
47 for ( int i = 0 ; i < n ; i ++){
48 if (q[i].dir=='A'){
49 cntA++;
50 a[cntA].beg = q[i].beg;
51 a[cntA].t = q[i].t;
52 }
53 else{
54 cntB++;
55 b[cntB].beg = q[i].beg;
56 b[cntB].t = q[i].t;
57 }
58 }
59 for ( int i = 0 ; i <= cntA ; i ++){
60 for ( int j = 0 ; j <= cntB ; j++){
61 dp[i][j][0]=dp[i][j][1]=inf/2; //正无穷溢出了....调了三个小时..妈蛋
62 }
63 }
64 dp[0][0][0]=dp[0][0][1]=0;
65}
66void solve(){
67 int l,r;
68 l = r = 0 ;
69 for ( int i = 0 ; i<= cntA ; i++){
70 for ( int j = 0 ; j <= cntB ; j++){
71 l = dp[i][j][1]-10;
72 r = dp[i][j][1]-10;
73 for ( int k = i+1 ; k<=cntA ; k++){
74 l = max(l+10,a[k].beg);
75 r = max(r+10,l+a[k].t);
76 dp[k][j][0] = min (r,dp[k][j][0]);
77 }
78 l = dp[i][j][0]-10;
79 r = dp[i][j][0]-10;
80 for ( int k = j+1 ; k<=cntB ; k++){
81 l = max(l+10,b[k].beg);
82 r = max(r+10,l+b[k].t);
83 dp[i][k][1] = min (r,dp[i][k][1]);
84 }
85 }
86 }
87}
88int main(){
89 int T;
90 cin>>T;
91 while (T--){
92 init();
93 solve();
94 int ans = 0 ;
95 ans = min (dp[cntA][cntB][0],dp[cntA][cntB][1]);
96 // printf("%d\n",ans);
97 cout<<ans<<endl;
98 }
99 return 0;
100}