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

2015-08-20 · 2 min read · 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!

  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}