ZJU/ZOJ 1428 Magazine Delivery 解题报告

题目大意是有3辆车初始停在1号站，要到i号站需要先到i-1号站，三辆车不能同时运行，一辆运行时另外两辆要停止，求到达n号站的最短时间。

很明显具备了最优子结构和无后效性的特点，故可以用到达的最末站点来划分阶段，汽车位置来表示状态。则f[i,j,k,l]表示到达的最末站点是i站时，第一辆车停在j号站，第二辆车停在k号站，第三辆车停在l号站所需的最少时间。状态转移方程是f[i,i,k,l]=min(f[i,i,k,l],f[i-1,j,k,l]+d[j,i]);f[i,j,i,l]=min(f[i,j,i,l],f[i-1,j,k,l]+d[k,i]);f[i,j,k,i]=min(f[i,j,k,i],f[i-1,j,k,l]+d[l,i]);(1<=i<=n,1<=j,k,l<=i-1)。最后在f[n,n,k,l]、f[n,j,n,l]、f[n,j,k,n]中找出最小值输出即可。由于状态f[i]只与f[i-1]有关，故可以用滚动数组降低空间复杂度。

3019777 2008-08-03 18:14:54 Accepted 1428 FPC 00:00.01 512K IwfWcf