BZOJ4244:邮戳拉力赛
? 解题记录 ? ? BZOJ ? ? 动态规划 ?    2018-12-19 11:55:14    346    0    0

【题目描述】
IOI铁路是由N+2个站点构成的直线线路。这条线路的车站从某一端的车站开始顺次标号为0...N+1。

这条路线上行驶的电车分为上行电车和下行电车两种,上行电车沿编号增大方向行驶,下行电车沿编号减小方向行驶。乘坐这两种电车的话,移动1站的距离需要T秒。换句话说,乘坐上行电车从车站i走到车站i+1需要T秒,称作下行电车从车站i走到车站i-1也需要T秒。你不能在0号车站乘坐下行电车,或在N+1号车站乘坐上行电车。由于电车发车的频率非常高,你可以无视等待电车消耗的时间。

每个车站设有上行电车的站台和下行电车的站台,连接两个站台的道路上设有邮戳台。

现在,IOI铁路召开了邮戳拉力赛。在拉力赛中,选手需要从0号车站的上行电车站台出发,在1...N号车站各盖一枚邮戳,最终到达N+1号车站的上行电车站台即可完成。

为了在每个车站盖上邮戳,必须从电车上下来,步行走到车站通路上的邮戳台。在i号车站的上行电车站台、邮戳台、下行电车站台之间移动所消耗的时间如下所示:

从车站i的上行电车站台到邮戳台的时间为Ui秒

从车站i的邮戳台到上行电车站台的时间为Vi秒

从车站i的下行电车站台到邮戳台的时间为Di秒

从车站i的邮戳台到下行电车站台的时间为Ei秒

邮戳拉力赛的选手只能访问0号车站与N+1号车站各一次。1...N号车站都可以访问任意多次。

 

现在给出有邮戳台的车站个数、乘坐电车移动一站的时间、在每个车站的上行电车站台、邮戳台、下行电车站台之间移动所消耗的时间,请你求出完成邮戳拉力赛的最短时间。

这个时间包括从0号车站出发,按下N个邮戳后到达N+1号车站的时间。无视等车的时间和按邮戳的时间。

【输入】
第一行两个空格分隔的整数N和T,表示有N+2个车站,电车行驶一站的距离需要T秒

接下来N行,第i行有四个空格分隔的整数Ui,Vi,Di,Ei,分别表示:

从车站i的上行电车站台到邮戳台的时间为Ui秒

从车站i的邮戳台到上行电车站台的时间为Vi秒

从车站i的下行电车站台到邮戳台的时间为Di秒

从车站i的邮戳台到下行电车站台的时间为Ei秒

【输出】
输出一行一个整数,表示完成邮戳拉力赛的最短时间。

【输入样例】
4 1
1 1 1 1
1 9 9 1
9 9 1 1
1 9 9 1
【输出样例】
23
【提示】
v>从车站0出发,按照2-1-4-3-1-5的顺序访问车站可以达到最短时间。

1≤N≤3000

1≤T≤10^5

1≤Ui≤10^5(1≤i≤N)

1≤Vi≤10^5(1≤i≤N)

1≤Di≤10^5(1≤i≤N)

1≤Ei≤10^5(1≤i≤N)

简单的dp套路,直接dp走的过程是不好做的,我们dp路径形状。

发现路径如果要反向往回,一定要在以前一个地方掉头走到终点。

我们把从下行站到上行站的过程看作左括号,

把从上行站到下行站的过程看作右括号。

这样有一个左括号一定就要有一个右括号。

就可以设f(i,j)表示到i这个位置有j个左括号没匹配。

考虑每一个点被覆盖的情况可以是一个括号,或者是直走时进去顺便经过。

注意一个地方可以重复放多个括号,复杂度是O(n^3)。

转移需要再用一个类似背包的dp优化一下,

每一次考虑在不在原来的基础上再放,复杂度降为O(n^2)。

要注意一些小细节,比如在j=0时是不能从下面经过点i的。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int maxn = 3e3 + 5;
LL dp[maxn][maxn], b[maxn];
int n, T;
int o_u[maxn], o_d[maxn], d_o[maxn], u_o[maxn];

inline void ref(LL &x, const LL &a) {
	x = min(x, a);
}

int main() {
	memset(dp, 0x3f, sizeof(dp));
	scanf("%d%d", &n, &T);
	for(register int i = 1; i <= n; ++i)
		scanf("%d%d%d%d", &u_o[i], &o_u[i], &d_o[i], &o_d[i]);
	dp[0][0] = 0;
	for(register int i = 1; i <= n; ++i) {
		memset(b, 0x3f, sizeof(b));
		b[0] = dp[i - 1][0] + T;
		//ref(dp[i][0], b[0]);
		for(register int j = 1; j <= n; ++j) {
			ref(b[j], b[j - 1] + d_o[i] + o_u[i]);
			ref(b[j], dp[i - 1][j - 1] + 1ll * (2 * (j - 1) + 1) * T + d_o[i] + o_u[i]);
			ref(dp[i][j], b[j]);
		}
		memset(b, 0x3f, sizeof(b));
		b[n] = dp[i - 1][n] + 1ll * (2 * n + 1) * T;
		//ref(dp[i][n], b[n]);
		for(register int j = n - 1; j >= 0; --j) {
			ref(b[j], b[j + 1] + u_o[i] + o_d[i]);
			ref(b[j], dp[i - 1][j + 1] + 1ll * (2 * (j + 1) + 1) * T + u_o[i] + o_d[i]);
			ref(dp[i][j], b[j]);
		}
		ref(dp[i][0], dp[i - 1][0] + u_o[i] + o_u[i] + T);
		for(register int j = 1; j <= n; ++j) {
			ref(dp[i][j], dp[i - 1][j] + d_o[i] + o_d[i] + 1ll * (2 * j + 1) * T);
			ref(dp[i][j], dp[i - 1][j] + u_o[i] + o_u[i] + 1ll * (2 * j + 1) * T);
		}
	}
	printf("%lld", dp[n][0] + T);
	return 0;
} 


上一篇: BZOJ2801:[Poi2012]Minimalist Security

下一篇: SP3713 PROOT - Primitive Root

346 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航