[JOISC2014]スタンプラリー

题目大意：

有\(n(n\le3000)\)个车站，另有一个起点站和终点站，所有车站排成一条链，相邻两个车站之间的距离为\(t\)。每个车站都有一个上行站台、一个下行站台。除起点站和终点站外，每个站点都有一个超市，超市在上行站台和下行站台之间。对于站点\(i\)，从上行站台到超市的时间为\(u_i\)，从超市到上行站台的时间为\(v_i\)，从下行站台到超市的距离为\(d_i\)，从超市到下行站台的距离为\(e_i\)。问从起点站出发，经过所有超市到达终点站的最短路。

思路：

\(f[i][j]\)表示前\(i\)个车站，下行转上行次数-上行转下行的次数为\(j\)的最短路。

考虑在一个站台是何种情况，分类讨论并相应转移即可。

时间复杂度\(\mathcal O(n^2)\)。

源代码：

#include<cstdio>

#include<cctype>

#include<climits>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=3001;

int f[N][N];

inline void upd(int &a,const int &b) {

	a=std::min(a,b);

}

int main() {

	const int n=getint(),t=getint();

	f[0][0]=INT_MIN;

	for(register int i=1;i<=n;i++) {

		const int u=getint(),v=getint(),d=getint(),e=getint();

		for(register int j=1;j<=n;j++) f[i-1][j]+=t*j*2;

		for(register int j=0;j<=n;j++) {

			upd(f[i][j],f[i-1][j]+u+v);//上行->邮戳->上行

			if(j!=0) upd(f[i][j],f[i-1][j]+d+e);//下行->邮戳->下行

			if(j!=n) upd(f[i][j],f[i-1][j+1]+u+e);//上行->邮戳->下行

			if(j!=0) upd(f[i][j],f[i-1][j-1]+d+v);//下行->邮戳->上行

		}

		for(register int j=n-1;j>=0;j--) {

			upd(f[i][j],f[i][j+1]+u+e);//上行->邮戳->下行

		}

		for(register int j=1;j<=n;j++) {

			upd(f[i][j],f[i][j-1]+d+v);//下行->邮戳->上行

		}

	}

	printf("%d\n",f[n][0]+t*(n+1)-INT_MIN);

	return 0;

}