记录编号	43236	评测结果	AAAAAAAAAA
题目名称	装配线调度	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2012-10-08 20:17:30	内存使用	2.41 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10000 + 10;
int n, e[3], x[3];
int a[3][N], t[3][N];
int l[3][N], L, F = 0x7ffffff;
void DFS(int d, int s, int k) {
	if(d > n) {
			F = min(F, s + x[k]);
	} else {
		if(k == 1) DFS(d+1, s + a[1][d], 1);
		else DFS(d+1, s + a[1][d] + t[2][d-1], 1);
		if(k == 2) DFS(d+1, s + a[2][d], 2);
		else DFS(d+1, s + a[2][d] + t[1][d-1], 2);
	}
}
int DFS(int k, int s) {
	if(s == 1) {
		return e[k] + a[k][1];
	} else {
		int r[3] = {0};
		r[k] = DFS(k, s-1);
		r[3-k] = DFS(3-k, s-1) + t[3-k][s-1];
		return min(r[1] + a[k][s], r[2] + a[k][s]);
	}
}
int f[3][N];
void Fastest_Way() {
	f[1][1] = e[1] + a[1][1];
	f[2][1] = e[2] + a[2][1];
	for(int j=2; j<=n; j++) {
		f[1][j] = min(f[1][j-1], f[2][j-1] + t[2][j-1]) + a[1][j];
		f[2][j] = min(f[2][j-1], f[1][j-1] + t[1][j-1]) + a[2][j];
		l[1][j] = (f[1][j] == f[1][j-1] + a[1][j]) ? 1 : 2;
		l[2][j] = (f[2][j] == f[1][j-1] + t[1][j-1] + a[2][j]) ? 1 : 2;
	}
	if(f[1][n] + x[1] <= f[2][n] + x[2])
		F = f[1][n] + x[1], L = 1;
	else F = f[2][n] + x[2], L = 2;
}
void Print_Stations(int k, int d) {
	if(!d) return;
	Print_Stations(l[k][d], d - 1);
	printf("%d ", k);
}
int main() {
	freopen("als.in", "r", stdin);
	freopen("als.out", "w", stdout);
	scanf("%d", &n);
	scanf("%d%d", e+1, x+1);
	scanf("%d%d", e+2, x+2);
	for(int i=1; i<=n; i++) scanf("%d", a[1]+i);
	for(int i=1; i<=n; i++) scanf("%d", a[2]+i);
	for(int i=1; i<n; i++) scanf("%d", t[1]+i);
	for(int i=1; i<n; i++) scanf("%d", t[2]+i);
	//DFS(2, e[1] + a[1][1], 1);
	//DFS(2, e[2] + a[2][1], 2);
	//F = min(DFS(1, n) + x[1], DFS(2, n) + x[2]);
	Fastest_Way();
	printf("%d\n", F);
	Print_Stations(L, n);
	//for(int i=1; i<=n; i++) printf("%d ", l[i]);
	return 0;
}