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; }
No comments:
Post a Comment