[POJ] Problem 3782 - Equal Sum Partitions

Posted on | In ,

An equal sum partition of a sequence of numbers is a grouping of the numbers (in the same order as the original sequence) in such a way that each group has the same sum. For example, the sequence:
2 5 1 3 3 7

may be grouped as:
(2 5) (1 3 3) (7)

to yield an equal sum of 7.

Note: The partition that puts all the numbers in a single group is an equal sum partition with the sum equal to the sum of all the numbers in the sequence.

For this problem, you will write a program that takes as input a sequence of positive integers and returns the smallest sum for an equal sum partition of the sequence.

Time Limit: 1000MS
Memory Limit: 65536K

Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by
a decimal integer M, (1 ≤ M ≤ 10000), giving the total number of integers in the sequence. The remaining line(s) in the dataset consist of the values, 10 per line, separated by a single space. The last line in the dataset may contain less than 10 values.

Output

For each data set, generate one line of output with the following values: The data set number as a decimal integer, a space, and the smallest sum for an equal sum partition of the sequence.

Sample Input

3
1 6
2 5 1 3 3 7
2 6
1 2 3 4 5 6
3 20
1 1 2 1 1 2 1 1 2 1
1 2 1 1 2 1 1 2 1 1

Sample Output

1 7
2 21
3 2

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int P = sc.nextInt();

        if (P < 1 || P > 1000)
            return;

        for (int i = 1; i <= P; i++) {
            int p = sc.nextInt();
            int M = sc.nextInt();

            if (M < 1 || M > 10000)
                return;

            int[] sum = new int[M + 1];

            for (int j = 1; j <= M; j++) {
                int m = sc.nextInt();
                sum[j] = sum[j - 1] + m;
            }

            int result = equalSumPartitions(sum);

            System.out.println(p + " " + result);
        }
    }

    private static int equalSumPartitions(int[] sum) {
        int n = sum.length - 1;
        int[][] dp = new int[n + 1][n + 1];

        for (int len = 1; len <= n; len++) {
            for (int i = 1; i <= n; i++) {
                int j = i + len - 1;

                if (j > n)
                    break;

                dp[i][j] = sum[j] - sum[i - 1];

                for (int k = i; k < j; k++) {
                    if (sum[j] - sum[k] == dp[i][k])
                        dp[i][j] = Math.min(dp[i][j], dp[i][k]);

                    if (sum[k] - sum[i - 1] == dp[k + 1][j])
                        dp[i][j] = Math.min(dp[i][j], dp[k + 1][j]);

                    if (dp[i][k] == dp[k + 1][j])
                        dp[i][j] = Math.min(dp[i][j], dp[i][k]);
                }
            }
        }

        return dp[1][n];
    }
}