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 , , ..., , 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, 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 t_i and b_i separated by blanks, where t_i ( 2 t_i 1000) indicates the duration in minutes specified by Professor Farnsworth for the trip (t_i is always even) and b_i ( 0 b_i 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;
}