pgm14_12.txt

c#版本 算法大全 几乎所有常见的算法 This file contains the C# code from Program

//
//   This file contains the C# code from Program 14.12 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C#"
//   by Bruno R. Preiss.
//
//   Copyright (c) 2001--2002 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.brpreiss.com/books/opus6/programs/pgm14_12.txt
//
public class Example
{
    public static void Typeset(int[] l, int D, int s)
    {
	int n = l.Length;
	int[,] L = new int[n, n];
	for (int i = 0; i < n; ++i)
	{
	    L[i, i] = l[i];
	    for (int j = i + 1; j < n; ++j)
		L[i, j] = L[i, j - 1] + l[j];
	}
	int[,] P = new int[n, n];
	for (int i = 0; i < n; ++i)
	    for (int j = i; j < n; ++j)
	    {
		if (L[i, j] < D)
		    P[i, j] = Math.Abs(D - L[i, j] - (j-i)*s);
		else
		    P[i, j] = int.MaxValue;
	    }
	int[,] c = new int[n, n];
	for (int j = 0; j < n; ++j)
	{
	    c[j, j] = P[j, j];
	    for (int i = j - 1; i >= 0; --i)
	    {
		int min = P[i, j];
		for (int k = i; k < j; ++k)
		{
		    int tmp = P[i, k] + c[k + 1, j];
		    if (tmp < min)
			min = tmp;
		}
		c[i, j] = min;
	    }
	}
    }
}