uva 12222 - Mountain Road(dp+贪心）

题目链接：uva 12222 - Mountain Road

题目大意：给出n，表示有n辆车，每辆车有三个值，分别代表说车的终点，发车时间，以及到移动所需的最小时间。因为路是单行道，所以不可以有两个不同方向的车同时存在和超车，并且相同方向的车有一个安全距离，为10，即全程都要相差10秒，问说所有车都到达目的地的最小时间。

解题思路：dp[i][j][k]表示说到A的i辆车，到B的j辆车，然后k表示说该从A地发车还是B地发车。然后同一方向的车的发车顺序按照贪心的思想，完全可以然s小的先发车。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 205;
const int INF = 0x3f3f3f3f;

struct car {
	int s, t;
}A[N], B[N];

int n, ca, cb, dp[N][N][2];

void init () {
	scanf("%d%*c", &n);
	ca = cb = 0;
	char ch[N];
	for (int i = 0; i < n; i++) {
		scanf("%s", ch);
		if (ch[0] == ‘A‘) {
			ca++;
			scanf("%d%d", &A[ca].s, &A[ca].t);
		} else {
			cb++;
			scanf("%d%d", &B[cb].s, &B[cb].t);
		}
	}
}

int solve () {
	memset(dp, INF, sizeof(dp));
	dp[0][0][0] = dp[0][0][1] = 0;
	for (int i = 0; i <= ca; i++) {
		for (int j = 0; j <= cb; j++) {
			int s = dp[i][j][0], end = 0;
			for (int k = i+1; k <= ca; k++) {
				s = max(s, A[k].s);
				end = max(s + A[k].t, end);
				dp[k][j][1] = min(dp[k][j][1], end);
				s += 10; end += 10;
			}

			s = dp[i][j][1]; end = 0;
			for (int k = j + 1; k <= cb; k++) {
				s = max(s, B[k].s);
				end = max(s + B[k].t, end);
				dp[i][k][0] = min(dp[i][k][0], end);
				s += 10; end += 10;
			}
		}
	}
	return min(dp[ca][cb][0], dp[ca][cb][1]);
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init ();
		printf("%d\n", solve () );
	}
	return 0;
}

uva 12222 - Mountain Road(dp+贪心）,布布扣,bubuko.com

uva 12222 - Mountain Road(dp+贪心）

原文：http://blog.csdn.net/keshuai19940722/article/details/21280259