Cow Exhibition (POJ 2148)

This problem is a little hard. To solve this problem we have let $DP[i][s]$ denotes the greatest possible $TF$ with first $i$ cows and $TS = s$. We first ignore all $TS < 0$ but reserve $TF < 0$ in the values of $DP[i][s]$. The iteration formular will be:

$$DP[i + 1][s] = \max\left\{DP[i][s - S_i] + F_i\right\}$$

Where $S_i$ and $F_i$ are respectively the smartness and funness of the $i$th cow. After optimize space cost and iteration order, we have:

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

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

public class CowExhibition {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        Cow[] cows = new Cow[N];
        for (int i = 0; i < N; i++) {
            cows[i] = new Cow(in.nextInt(), in.nextInt());
        }
        Arrays.sort(cows);
        long[] dp = new long[102000];
        Arrays.fill(dp, -102000);
        dp[0] = 0;
        int maxs = 0;
        for (int i = 0; i < N; i++) {
            Cow c = cows[i];
            if (c.s >= 0) {
                for (int j = maxs + c.s; j >= c.s; j--) {
                    dp[j] = Math.max(dp[j], dp[j - c.s] + c.f);
                }
            } else {
                for (int j = 0; j <= maxs + c.s; j++) {
                    dp[j] = Math.max(dp[j], dp[j - c.s] + c.f);
                }
            }
            maxs = Math.max(maxs, maxs + c.s);
        }
        long max = 0;
        for (int i = 0; i <= maxs; i++) {
            if (dp[i] >= 0) max = Math.max(max, i + dp[i]);
        }
        System.out.println(max);
    }
}