BZOJ4244：邮戳拉力赛

【题目描述】
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;
}

Rockdu's Blog