UVA12222 山路

题意：

- - 一个山路只有一条车道，因此不能有两辆方向相反的车同时在车道内。同时，为了保证安全，车道内不能超车，且同向行驶的车间距必须大于10分钟。现在给你n辆车，三个参数依次表示行驶方向，到达时刻，行驶时间。问如何安排能使最后一个通过的车通过时的时刻最小，输出这个值。

------------

分析：
我们如果只考虑一边来车的情况，会发现，一定是先到的先走，否则不是最优。因此，最优解一定是形如A1，A2，A3，B1，B2，A4，B3，B4的序列，即走一段连续的A,再走一段连续的B,再走一段连续的A......一定不会出现A2先过，A1才过的情况。
题解:
考虑DP，设fi,j,k表示过了i辆车，其中有j辆A,最后一辆是A（k==0）/B（k==1）的最小时刻。

显然，初始时f[0][0][1]=f[0][0][0]=0，f[i][j][0/1]=inf

考虑状态转移：
设cnta为A的总数，cntb为B的总数，numb=i-j

1. f[i+x][j+x][0]=min(f[i][j][1]+mt),1<=x<=cnta-j。x表示i之后连续通过的A的数量，即从i+1到i+x全部过A,mt表示连续x辆A通过的最小时刻（mt的计算见代码）。

1. f[i+x][j][1]=min(f[i][j][0]+mt)，1<=x<=cntb-numb,x表示i之后连续通过的B的数量，即从i+1到i+i+x全部过B，mt表示连续x辆B通过的最小时刻。

最终答案为min（f[n][cnta][1],f[n][cnta][0]），总时间复杂度O（n³）

#include<bits/stdc++.h>
using namespace std;
const int N=206;
const int inf=2e9+555;
struct node{
    int s,d;
}a[N],b[N];
char c;
int f[N][N][2],n,cnta,cntb,T;
int main(){
    cin>>T;
    while(T--){
        memset(f,0x3f,sizeof f);
        cin>>n;
        cnta=0,cntb=0;
        for(int i=1,u,v;i<=n;i++){
            cin>>c;
            cin>>u>>v;
            if(c=='A') a[++cnta]={u,v};
            else b[++cntb]={u,v};
        }
        f[0][0][0]=f[0][0][1]=0;        
        for(int i=0;i<=n;i++){
            for(int j=max(0,i-cntb);j<=i&&j<=cnta;j++){
                int numb=i-j,st,mt;
                mt=st=f[i][j][1];
                for(int x=1;x<=cnta-j;x++){
                    if(x==1) st=max(st,a[x+j].s),mt=st+a[x+j].d;
                    else st=max(st+10,a[x+j].s),mt=max(mt+10,st+a[x+j].d);
                    f[i+x][x+j][0]=min(f[i+x][x+j][0],mt);
                }
                st=mt=f[i][j][0];
                for(int x=1;x<=cntb-numb;x++){
                    if(x==1) st=max(st,b[x+numb].s),mt=st+b[x+numb].d;
                    else st=max(st+10,b[x+numb].s),mt=max(mt+10,st+b[x+numb].d);
                    f[i+x][j][1]=min(mt,f[i+x][j][1]);
                }
            }
        }
        cout<<min(f[n][cnta][1],f[n][cnta][0])<<endl;
    }
    return 0;
}