UVA - 12222 Mountain Road

问题

一条山路，单行道，双向来车，通向的车之间的距离（通过同一个点）要保持10s以上，问所有车通行的最短时间（车子在到达路的一端后可以等待任意时间，再行驶）

分析

分为两个方向单独考虑，dp[i][j][0/1]分别代表A向行驶完i辆，B向行驶完j辆，最后一辆车时A向/B向的车时所花费的最短时间
只有行驶的汽车方向变向，才发生状态转移

#include<iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=205,maxm=35,Inf=0x3f3f3f3f;
struct Car{ 
   
    int t,d;
    Car(int t=0,int d=0):t(t),d(d){ 
   }
}A[maxn],B[maxn];
int kase,n,t,d,acnt,bcnt, dp[maxn][maxn][2];
char ch;
int main(void){ 
   
    scanf("%d",&kase);
    while(kase--){ 
   
        scanf("%d",&n);
        acnt=0;
        bcnt=0;
        for(int i=0;i<n;++i){ 
   
            scanf(" %c%d%d",&ch,&t,&d);
            if(ch=='A'){ 
   
                A[++acnt]=Car(t,d);
            }else{ 
   
                B[++bcnt]=Car(t,d);
            }
        }
        memset(dp,Inf,sizeof(dp));
        dp[0][0][0]=dp[0][0][1]=0;
        //使用刷表法
        //行驶的汽车方向变向，发生状态转移（同向行驶的汽车当作是一批，不会使结果变坏）
        for(int i=0;i<=acnt;++i){ 
   
            for(int j=0;j<=bcnt;++j){ 
   
                int optime=dp[i][j][1],edtime=0; //A[k]的开始时间和结束时间
                for(int k=i+1;k<=acnt;++k){ 
   
                    optime=max(optime,A[k].t); //A[k]的开始时间，推迟开车
                    edtime=max(edtime,optime+A[k].d);  //A[k]的结束时间，因为要保持10s，所以要有所延迟
                    dp[k][j][0]=min(dp[k][j][0],edtime);
                    optime+=10;  //同向至少10s后才能行驶
                    edtime+=10;  //同理，至少10s后才能到达下一辆
                }

                optime=dp[i][j][0],edtime=0;
                for(int k=j+1;k<=bcnt;++k){ 
   
                    optime=max(optime,B[k].t);
                    edtime=max(edtime,optime+B[k].d);
                    dp[i][k][1]=min(dp[i][k][1],edtime);
                    optime+=10;
                    edtime+=10;
                }
            }
        }
        printf("%d\n",min(dp[acnt][bcnt][0],dp[acnt][bcnt][1]));
    }
}