POJ - 3846 Mountain Road

题意：有一条单行道，可以有A，B两个方向的行驶，每辆车有通过这条路的方向，到达这条路的时间，通过的时间，每两辆相邻的车通过同一个地点的时间差必须>=10，求所有车通过的最短时间

思路：dp[i][j][2],表示A方向的前i辆，B方向的前j辆，以及最后一辆通过的方向是A或者B的最短时间，注意条件时间差>=10

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 210;
const int INF = 0x3f3f3f3f;

struct car{
    int start,len;
    car(){};
    car(int a,int b){
        start = a,len = b;
    }
}a[MAXN],b[MAXN];
char str[2];
int dp[MAXN][MAXN][2],n;

void DP(int n,int m){
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k < 2; k++)
                dp[i][j][k] = INF;
    dp[0][0][0] = dp[0][0][1] = 0;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++){
            int s = dp[i][j][0],t = s;
            for (int k = j+1; k <= m; k++){
                s = max(s,b[k].start);
                t = max(t,s+b[k].len);
                dp[i][k][1] = min(dp[i][k][1],t);
                s += 10,t += 10;
            }
            s = dp[i][j][1],t = s;
            for (int k = i+1; k <= n; k++){
                s = max(s,a[k].start);
                t = max(t,s+a[k].len);
                dp[k][j][0] = min(dp[k][j][0],t);
                s += 10,t += 10;
            }
        }
}

int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        int p = 0,q = 0;
        while (n--){
            int s,l;
            scanf("%s %d %d",str,&s,&l);
            if (str[0] == ‘A‘)
                a[++p] = car(s,l);
            else b[++q] = car(s,l);
        }
        DP(p,q);
        printf("%d\n",min(dp[p][q][0],dp[p][q][1]));
    }
    return 0;
}

POJ - 3846 Mountain Road

原文：http://blog.csdn.net/u011345136/article/details/18924737