simplefastestway.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 58 行

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//19 Feb 2008
package cn.edu.whu.iss.algorithm.unit15.assemble;

public class SimpleFastestWay extends AbstractFastestWay {

	public SimpleFastestWay() {
		super();
	}

	public SimpleFastestWay(int[][] a, int[][] t, int[] e, int[] x, int n) {
		super(a, t, e, x, n);
	}

	public int fastestWay() {
		int[][] f = new int[2][2];
		l = new int[2][n];
		int nowi = 0;
		int nowj = 0;
		int j = 0;
		for (nowi = 0; nowi < 2; nowi++) {
			f[nowi][nowj] = e[nowi] + a[nowi][j];
		}
		while (j < n - 1) {
			j++;
			nowj = 1 - nowj;
			for (nowi = 0; nowi < 2; nowi++) {
				int p = f[nowi][1 - nowj] + a[nowi][j];
				int q = f[1 - nowi][1 - nowj] + t[1 - nowi][j - 1] + a[nowi][j];
				if (p <= q) {
					f[nowi][nowj] = p;
					l[nowi][j] = nowi+1;
				} else {
					f[nowi][nowj] = q;
					l[nowi][j] = 2-nowi;
				}
			}
		}
		if (f[0][nowj] + x[0] <= f[1][nowj] + x[1]) {
			ft = f[0][nowj] + x[0];
			lt = 1;
		} else {
			ft = f[1][nowj] + x[1];
			lt = 2;
		}
		return ft;
	}

}