UVa 1196

an easy DP problem
state:
    dp[i][j] - maximum height when block(s) of l=i and m=j is(are) on top
transition:
    dp[i][j]+=max(dp[i-1][j], dp[i][j-1])
    each step we have two choices...

/* UVas */
/*****************************************************************************/
struct block {
    int l, m;
} b[10000];
int n;
int d[101][101];
int main(void) {
    while (scanf("%d", &n)>0&&n) {
        memset(d, 0, sizeof(d));
        for (int i=0; i<n; i++) {
            scanf("%d %d", &b[i].l, &b[i].m);
            d[b[i].l][b[i].m]++;
        }
        int r=0;
        for (int i=1; i<=100; i++)
            for (int j=1; j<=100; j++) {
                d[i][j]+=max(d[i-1][j], d[i][j-1]);
                r=max(r, d[i][j]);
            }
        printf("%d\n", r);
    }
    printf("*\n");
}
/*****************************************************************************/