USACO OCT06 2006 Problem 'lineup' Analysis

by Rob Kolstad

This is the absolutely classic dynamic programming problem that USACO alumni know as 'Buy Low, Buy Lower'. In this incarnation, the goal is to find the longest ordered subset of increasing integers from a set.

Recursion is usually the first idea, but the combinatoric explosion quickly dooms it for relatively small N. Work your way through the USACO training pages for a long-winded explanation of how the following program by South Africa coach Bruce Merry works:

#include <fstream>
#include <algorithm>

using namespace std;

#define MAXN 5005

int main() {
    ifstream in ("lineup.in");
    int N;
    int v[MAXN];
    int b[MAXN];
    int ans = 1;

    in >> N;
    for (int i = 0; i < N; i++)
        in >> v[i];
    for (int i = 0; i < N; i++) {
        b[i] = 1;
        for (int j = 0; j < i; j++)
            if (v[j] < v[i])
                ans >?= b[i] >?= 1 + b[j];
    }
    ofstream out("lineup.out");
    out << ans << "\n";
    return 0;
}

And if you're looking for even more speed, you can insert a half-interval search as Poland's Tomasz Kulczynski did:

#include <cstdio>
using namespace std;

#define M 5057
#define inf ((int)((1U<<31)-1))

int n,m,i,a[M],t[M],p,q,s;

int main () {
    freopen ("lineup.in","r",stdin);
    freopen ("lineup.out","w",stdout);
    scanf ("%d",&n);
    for (i = 0; i < n; i++) scanf ("%d",&a[i]);
    t[0] = inf;
    for (i = 0; i < n; i++) {
        p = 0; q = m;
        while (p < q) {
            s =  (p+q)/2;
            if (t[s] >= a[i]) q = s;
            else p = s+1;
        }
        t[p] = a[i];
        if (p == m) t[++m] = inf;
    }
    printf ("%d\n",m);
    return 0;
}