Spoj_00453_Sums_in_a_Triangle.java

Problem Links:
Spoj00453, Spoj06597,

Problem:

453. Sums in a Triangle (tutorial) Problem code: SUMTRIAN

This is problem SUMITR without strict source limit.

Let us consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line etc. Develop a program which will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:

• on each path the next number is located on the row below, more precisely either directly below or below and one place to the right;
• the number of rows is strictly positive, but less than 100;
• all numbers are positive integers between O and 99.

Input

In the first line integer n - the number of test cases (equal to about 1000). Then n test cases follow. Each test case starts with the number of lines which is followed by their content.

Output

For each test case write the determined value in a separate line.

Example

Input:
2
3
1
2 1
1 2 3
4 
1 
1 2 
4 1 2
2 3 1 1 

Output:
5
9

---

Solution:

1st, using two arrays (滚动数组 in Chinese) technology is the key to this problem, it saves a lot of memory and also helps to implement the dynamic programming. The pros is it could use less memory to solve the problem, while it could not backtrack the path, which results the maximum.
2nd, the trick I use is if the previous sum is 0 or not, which is the initial value for the declaration.
3rd, using stringtokenizer to split the string is much faster than the string.split API function. It took me 3 or 4 TLE to prove that. Also, from the blog of somebody, some research people did showed the same results.
4th, as the StringTokenizer return the next available element, the countTokens() will decrease. This problem take me more than 1 hour to figure it out.

Source Code:


//Fri Oct 14 20:09:41 PDT 2011
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(
                    System.in));
            int N = Integer.parseInt(br.readLine());
            for (int i = 0; i < N; i++) {
                int n = Integer.parseInt(br.readLine().trim());
                int[][] nums = new int[2][n];
                int mmax = 0;
                for (int j = 0; j < n; j++) {
                    StringTokenizer stk = new StringTokenizer(br.readLine()
                            .trim());
                    int len = stk.countTokens();
                    for (int k = 0; k < len; k++) {
                        int tmp = Integer
                                .parseInt(stk.nextElement().toString());
                        // System.out.print(tmp + ", ");
                        if (k > 0)
                            nums[j % 2][k] = Math.max(nums[1 - j % 2][k],
                                    nums[1 - j % 2][k - 1])
                                    + tmp;
                        else
                            nums[j % 2][k] = nums[1 - j % 2][k] + tmp;
                        mmax = Math.max(mmax, nums[j % 2][k]);
                        // System.out.print(tmp + ", ");
                    }
                    // System.out.println();
                }
                System.out.println();
                System.out.println(mmax);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}