题目链接: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太慢了,有时候UVa还会挂。 而且书里把输入输出样例省去了,这里整理出原题做个参考。 所以我把书里3-12章的每道例题和习题的UVa原题pdf下载整理。 上次上传的那个没有例题只有习题,...
UVa写入 使用C ++编写UVa OJ: : 等级 基于 ★★ ★★ ★★★ ★★★★ ★★★★★ 未排名
CPP中的Postfix-Tree-Calculator:在C ++中实现后缀树计算器。 包括来自UVA CS部门的测试C ++文件
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。