uva 12222——Mountain Road

刺骨的言语ヽ痛彻心扉 2022-08-18 12:16 23阅读 0赞

题意：有一个狭窄的山路，两辆车不能同时相向而行，并且同向的车的间隔不能小于10秒，给定一些车的起始时间，求最后一辆车离开的最短时间。

思路：递推，dp（i，j，k）表示A端过了i辆车，B端过了j辆车，下辆车从k端走的情况，对于A端下一个车枚举i+1的车情况更新，B端则枚举第j+1辆车来更新。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=9999999;//0x3fffffff;
    const int inf=-INF;
    const int N=1000000;
    const int M=2005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define ft(i,s,n) for (int i=s;i<=n;i++)
    #define frt(i,s,n) for (int i=s;i>=n;i--)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int len1,len2;
    int n,dp[M][M][2];
    struct node{
        int s,t;
    }g[2][M];
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while (T--){
            scanf("%d",&n);
            char c;
            int s,t;
            len1=len2=0;
            ft(i,1,n){
                getchar();
                //scanf("%c",&c);
                //printf("%c\n",c);
                scanf("%c%d%d",&c,&s,&t);
                if (c=='A'){
                    len1++;
                    g[0][len1].s=s;
                    g[0][len1].t=t;
                } else{
                    len2++;
                    g[1][len2].s=s;
                    g[1][len2].t=t;
                }
            }
            int ts,td;
            cls(dp,INF);
            dp[0][0][0]=dp[0][0][1]=0;
            ft(i,0,len1){
                ft(j,0,len2){
                    ts=dp[i][j][1],td=0;
                    ft(k,i+1,len1){
                        ts=max(ts,g[0][k].s);
                        td=max(td,ts+g[0][k].t);
                        dp[k][j][0]=min(dp[k][j][0],td);
                        ts+=10;td+=10;
                    }
                   ts=dp[i][j][0],td=0;
                    ft(k,j+1,len2){
                        ts=max(ts,g[1][k].s);
                        td=max(td,ts+g[1][k].t);
                        dp[i][k][1]=min(dp[i][k][1],td);
                        ts+=10;td+=10;
                    }
                }
            }
            printf("%d\n",min(dp[len1][len2][0],dp[len1][len2][1]));
        }
    }