[UVA][dp] 12324 - Philip J. Fry Problem
Philip J. Fry Problem
It's been a few months since Bender solved his famous bending problem. A special request has arrived to
Planet Express Inc., the interplanetary courier company where Bender works. Professor Farnsworth (founder, CEO, and
chairman of the board) immediately prepared the mission and summoned his crew: Philip J. Fry, Turanga Leela, and Bender.
To succeed in the mission, the crew has to make n trips | Philip J. Fry Problem |
, 
, ..., 
,
in the exact order established
by Professor Farnsworth. He has also provided the crew with a notebook
that specifies how many minutes each trip in the spaceship will take.
Nibbler, from Futurama.
©The Curiosity Company and 20thCentury Fox.
Nibbler, Leela's stupid pet, is also a member of the crew and a critical element to succeed in the mission. Nibbler's feces, which it expels every now and then, consist of spheres of dark matter that can be used to increase the speed of the spaceship. In fact, a sphere used during a trip halves its duration. Bender's role in the mission is to pick up the heavy spheres and put them in the reactor of the spaceship. However, he will never put two spheres during the same trip: the accumulation of dark matter is extremely dangerous and may destroy the spaceship.
In each trip of the mission, Nibbler expels a certain number of dark matter spheres that can be used to decrease the duration
of any of the upcoming trips. In other words, a sphere of dark matter produced during the trip 
can be used to duplicate the
speed of the spaceship in one of the trips 
, with
i < j 
n.
Fry is responsible for planning how to use the spheres to reduce the total travel time. Your task is to help Fry in determining
what is the minimum duration of the mission if he uses Nibbler's spheres cleverly.
Input
The input consists of several test cases. The first line of each case contains an integer n indicating the number of trips
(
1 n 100). Then, n lines follow describing each of the trips , , ..., : each line
contains two integers ti and bi separated by blanks, where ti (
2 ti 1000) indicates the duration in minutes
specified by Professor Farnsworth for the trip (ti is always even) and bi (
0 bi n) indicates the number
of dark matter spheres that Nibbler will expel during the trip . The last test case is followed by a line containing a
single `0'.
Output
For each test case, print a line with an integer number indicating the minimum time required to complete the mission.
Sample Input
2 24 1 10 0 2 10 1 24 0 3 10 0 24 0 38 0 3 10 1 24 0 14 0 3 10 1 24 0 38 0 3 10 1 24 1 38 0 3 10 3 24 0 38 1 0
Sample Output
29 22 72 36 53 41 41
題目描述：
一個生物跟著科學家旅行，根據輸入列的順序進行移動，而每階段的移動這生物可以獲得暗物質，
一個暗物質，可以使得接下來的某次旅行時間減半，假設我們可以預先知道每階段的資訊。
問全程的最少時間。
題目解法：
dp[i][j] 已經走到第 i 階段，當前有 j 個暗物質 的最少時間。
#include <stdio.h>
#include <algorithm>
using namespace std;
int dp[105][105];
int main() {
int n, t[105], b[105];
int i, j, k;
while(scanf("%d", &n) == 1 && n) {
for(i = 0; i < n; i++)
scanf("%d %d", &t[i], &b[i]);
for(i = 0; i <= n; i++)
for(j = 0; j <= n; j++)
dp[i][j] = 0xfffffff;
dp[0][0] = 0;
for(i = 0; i < n; i++) {
for(j = 0; j <= n; j++) {
int bb = min(j+b[i], n);
dp[i+1][bb] = min(dp[i+1][bb], dp[i][j]+t[i]);//not using.
if(j)//using.
dp[i+1][bb-1] = min(dp[i+1][bb-1], dp[i][j]+t[i]/2);
}
}
int ret = 0xfffffff;
for(i = 0; i <= n; i++)
ret = min(ret, dp[n][i]);
printf("%d\n", ret);
}
return 0;
}