当前位置:首页 » Project Euler » 详细页

Searching a triangular array for a sub-triangle having minimum-sum 题号:150 难度: 55 中英对照

In a triangular array of positive and negative integers, we wish to find a sub-triangle such that the sum of the numbers it contains is the smallest possible.

In the example below, it can be easily verified that the marked triangle satisfies this condition having a sum of −42.

We wish to make such a triangular array with one thousand rows, so we generate 500500 pseudo-random numbers sk in the range ±219, using a type of random number generator (known as a Linear Congruential Generator) as follows:

t := 0
for k = 1 up to k = 500500:
    t := (615949*t + 797807) modulo 220
    sk := t−219

Thus: s1 = 273519, s2 = −153582, s3 = 450905 etc

Our triangular array is then formed using the pseudo-random numbers thus:

s1
s2  s3
s4  s5  s6 
s7  s8  s9  s10
...

Sub-triangles can start at any element of the array and extend down as far as we like (taking-in the two elements directly below it from the next row, the three elements directly below from the row after that, and so on).
The "sum of a sub-triangle" is defined as the sum of all the elements it contains.
Find the smallest possible sub-triangle sum.


Solution

按照题目给出的递推方式求出三角形所有的数值,然后直接枚暴力举三角形的顶点和高度即可。

Code

public final class p150 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

	
    static public String run() {
		int[][] t = new int[1000][];
		long[][] s = new long[1000][];
		long tmp=0;
		for (int i = 0; i < 1000; ++i) {
			t[i] = new int[i + 1];
			s[i] = new long[i + 1];
			for (int j = 0; j <= i; ++j) {
				tmp = (615949 * tmp + 797807) % 1048576;
				t[i][j] = (int) (tmp - 524288);
			}
		}
		long min = 0;
		for (int use = 1; use <= 1000; ++use) {
			for (int j = 0; j < use; ++j)
				s[use - 1][j] = t[use - 1][j];
			for (int i = use - 1; i >= 0; --i) {
				for (int j = 0; j <= i; ++j) {
					long k = t[i][j];
					if (i < use - 1)
						k += s[i + 1][j] + s[i + 1][j + 1];
					if (i < use - 2)
						k -= s[i + 2][j + 1];
					s[i][j] = k;
					if (k < min)
						min = k;
				}
			}
		}
		return ""+min;
	}
	
}
-271248680
2885ms