HUST team contest #E A Mountain Road||poj 3846 (dp)

比赛的时候以为是贪心...

想了好久.

不过最后没敢写,因为没办法证明正确性,只是直觉==

最后剩下的时间给队友改另一道题了..

果然明智...

蠢的人的直觉真心不靠谱..

这题是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!

/*************************************************************************
	> File Name: code/2015summer/0821/E.cpp
	> Author: 111qqz
	> Email: rkz2013@126.com 
	> Created Time: 2015年08月21日 星期五 01时28分23秒
 ************************************************************************/
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#define y0 abc111qqz
#define y1 hust111qqz
#define yn hez111qqz
#define j1 cute111qqz
#define tm crazy111qqz
#define lr dying111qqz
using namespace std;
#define REP(i, n) for (int i=0;i<int(n);++i)  
typedef long long LL;
typedef unsigned long long ULL;
const int inf = 0x7fffffff;
const int N=2E2+7;
int dp[N][N][2];
int cntA,cntB;
struct Q{
    int beg,t;
    char dir;
}q[N],a[N],b[N];
void init(){
    int n;
    int beg,time;
    char dir;
    scanf("%d",&n);
     cntA = 0 ;
     cntB = 0 ;
    for ( int i = 0 ; i < n ;i++){
	cin>>q[i].dir>>q[i].beg>>q[i].t;
    }
    for ( int  i = 0 ; i < n ; i ++){
	if (q[i].dir=='A'){
	    cntA++;
	    a[cntA].beg = q[i].beg;
	    a[cntA].t = q[i].t;
	}
	else{
	    cntB++;
	    b[cntB].beg = q[i].beg;
	    b[cntB].t = q[i].t;
	}
    }
    for ( int i = 0 ; i <= cntA ; i ++){
	for ( int j = 0 ; j <= cntB ; j++){
	    dp[i][j][0]=dp[i][j][1]=inf/2; //正无穷溢出了....调了三个小时..妈蛋
	}
    }
    dp[0][0][0]=dp[0][0][1]=0;
}
void solve(){
    int l,r;
    l = r = 0 ;
    for ( int i = 0 ; i<= cntA ; i++){
	for ( int j = 0 ; j <= cntB ; j++){
	    l = dp[i][j][1]-10;
	    r = dp[i][j][1]-10;
	    for ( int k = i+1 ; k<=cntA ; k++){
 		l = max(l+10,a[k].beg);
		r = max(r+10,l+a[k].t);
		dp[k][j][0] = min (r,dp[k][j][0]);
	    }
	    l = dp[i][j][0]-10;
	    r = dp[i][j][0]-10;
	    for ( int k = j+1 ; k<=cntB ; k++){
	 	l = max(l+10,b[k].beg);
		r = max(r+10,l+b[k].t);
		dp[i][k][1] = min (r,dp[i][k][1]);
	    }
	}
    }
}
int main(){
    int T;
    cin>>T;
    while (T--){
	init();
	solve();
	int ans = 0 ;
	ans =  min (dp[cntA][cntB][0],dp[cntA][cntB][1]);
	//	printf("%d\n",ans);
	cout<<ans<<endl;
    }
	return 0;
}