Wooden Sticks (POJ 1065)

This problem is equivalent to asking you what is the minimum number of non-overlapping non-decreasing subsequence can be found in the sequence. A straight forward solution may be that each time we find the longest non-decreasing subsequence from the original sequence and remove the items. We do this repeatedly until no elements left. This solution is correct but not time efficient enough.

Here we have to apply a proposition that the number of non-decreasing sub sequence is at least the number of items of the longest decreasing subsequence in the original sequence. Let $x$ denote the number of items in the longest decreasing subsequence and $l$ denote the minimum number of non-decreasing subsequence. Assume $l < x$ then we first remove the items in the decreasing subsequence from the original sequence and then obviously we partition the remaining items into $l$ non-decreasing subsequence. Then we put items in our decreasing subsequence back to the $l$ groups of items. Obviously there must be at least two items be put into one group as $l < x$. But we note that the relative order of items in subsequence must be the same as that in the original sequence, so we have at least one group we contains two or more elements that is decreasing, thus that group can not be a non-decreasing subsequence. Here we find a contradiction, so we must hvae $l\ge x$.

So the answer to this problem is just the number of items in the longest decreasing subsequence of the origin sequence. We have to sort the sticks by their lengths first as a stick as two properties.

import java.io.*;
import java.util.*;

class Stick implements Comparable<Stick>{
    int l;
    int w;
    public Stick(int l, int w) {
        this.l = l;
        this.w = w;
    }
    public int compareTo(Stick that) {
        Stick a = this;
        Stick b = that;
        if (a.l < b.l) return -1;
        else if (a.l > b.l) return 1;
        else if (a.w < b.w) return -1;
        else if (a.w > b.w) return 1;
        else return 0;
    }
}

public class WoodenSticks {
    private static void solve(Stick[] sticks) {
        int N = sticks.length;
        int[] dp = new int[N];
        int max = 0;
        for (int i = 0; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (sticks[j].w > sticks[i].w) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int N = in.nextInt();
            Stick[] sticks = new Stick[N];
            for (int i = 0; i < N; i++) {
                sticks[i] = new Stick(in.nextInt(), in.nextInt());
            }
            Arrays.sort(sticks);
            solve(sticks);
        }
    }
}