UVa 12324 - Phillip J. Fry Problem

Problem Statement:
UVa 12324 - Phillip J. Fry Problem

Solution:
One of the classical dynamic programming problem. But might still be interesting to discuss.

Let S[i][k] be the minimum amount of time needed to finish trips [i..n]. Then the following relationship holds:
S[i][k] = min { S[i+1][k+b[i]] + t[i], S[i+1][k+b[i]-1] + t[i]/2 }
Direct implementation of this approach will result in a TLE at UVa, so you will need to prune the search space by considering the following observation: In a trip sequences with length n, you can consume at most n spheres. With that you can reduce the search space sufficiently to pass the time limit.



Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

/*
S[i][k] = minimum number of time needed to finish trip [i..n] starting with k spheres
S[i][k] = min S[i+1][k+b[i]] + t[i], S[i+1][k+b[i]-1] + t[i]/2
*/

int dp[103][10003];
int b[103];
int t[103];
int N;

void solve_faster() {
    for(int i=0;i<=N;++i)dp[N][i] = 0;
    for(int i=N-1;i>=0;--i){
        for(int k=0;k<=N;++k){
            dp[i][k] = 12345678;
            dp[i][k] = min(dp[i+1][min(N, k+b[i])] + t[i], dp[i][k]);
            if(k>0) dp[i][k] = min(dp[i+1][min(N, k+b[i]-1)] + t[i]/2, dp[i][k]);
        }
    }
    printf("%d\n",dp[0][0]);
}

void solve() {
    for(int i=0;i<=N*N;++i)dp[N][i] = 0;
    for(int i=N-1;i>=0;--i){
        for(int k=0;k<=N*N;++k){
            dp[i][k] = 12345678;
            if(k+b[i]>N*N) continue;
            dp[i][k] = min(dp[i+1][k+b[i]]+t[i], dp[i][k]);
            if(k>0) dp[i][k] = min(dp[i+1][k+b[i]-1]+t[i]/2, dp[i][k]);
        }
    }
    printf("%d\n", dp[0][0]);
}

int main(){
    while(scanf("%d",&N), N!=0){
        for(int i=0;i<N;++i){
            scanf("%d%d",&t[i],&b[i]);
        }
        solve_faster();
    }
    return 0;
}