装配线调度

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 als.in 输出文件 als.out
【问题描述】
已知某生产车间有两条装配线,每条有N个装配站。装配线i的第j个装配站表示为Si,j。在该站的装配时间为ai,j。一个汽车底盘进入工厂,然后进入装配线i(i=1 或 i=2),花费时间为ei。在通过一条线的第j个装配站后,这个底盘来到任一条线的第(j+1)个装配站。如果它留在相同的装配线,则没有移动的开销。但是,如果在装配站的Si,j后,移动到了另外一条线上,则花费时间ti,j。在离开一条线的第n个装配站后,完成的汽车花费时间xi后离开工厂。待求解的问题是应该在装配线1选择那些站,在装配线2选择那些站,才能使汽车通过工厂的时间最小
【输入格式】 
第一行输入一个数字n,每条装配线上有n个装配站。 
第二、三行各有2个数字,表示两条装配线进入、离开的时间。 
第四、五行各有n个数字,表示两条装配线每个站点的装配时间。 
第六、七行各有n-1个数字,表示两条装配线之间切换的时间。
【输出格式】 
第一行1个数字,表示总的最短装配时间 
第二行共n(1<=N<=10000)个数字,即经过的站点所在装配线的序号。 若有多种方案,输出字典序最小的方案。
【输入输出样例】
als.in

2 3 
4 2 
7 9 3 4 8 4 
8 5 6 4 5 7 
2 3 1 3 4 
2 1 2 2 1
als.out
38 
1 2 1 2 2 1