USACO February 2006 Problem 'treat/trt' Analysis

by Bruce Merry

This problem can be solved by dynamic programming. Consider starting with a particular pair of treats exposed. This pair determines how much time has already passed and thus how much the remaining treats are worth. At this point there are two choices, corresponding to the two treats that can be removed. The return on each treat is known, and in each case dynamic programming will give the return on the remaining treats. It is thus possible to compute the optimal return for the starting pair in O(N²) time. With proper sequencing it is also possible to use only O(N) memory, although that optimisation is not necessary here.

USA's Robert Mitchell Burke submitted this Java solution:

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

public class treat {
    public static void main(String[] NEVAR_USE_THIS_VARIABLE353512) throws Throwable {
        BufferedReader in=new BufferedReader(new FileReader("treat.in"));
        PrintWriter out=new PrintWriter("treat.out");
        
        int N=Integer.parseInt(in.readLine());
        int[] v=new int[N];

        for(int i=0;i<v.length;i++)
            v[i]=Integer.parseInt(in.readLine());

        int[] prev=new int[N+4];
        int[] dp=new int[N+4];

        for(int i=1;i<=N;i++) {
            for(int k=0;k<i;k++) {
                dp[k]=Math.max(dp[k],prev[k]+(i*v[N-i+k]));
                dp[k+1]=Math.max(dp[k+1],prev[k]+(i*v[k]));
            }
            prev=dp;
            dp=new int[N+4];
        }
        int max=0;
        for(int i:prev)
            max=Math.max(max,i);
        out.println(max);
        out.close();
        System.exit(0);
    }
}