Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

In the year 2020, a race of atomically energized cars will b e held. Unlike today's car races, fueling is not a concern of racing teams. Cars can run throughout the course without any refueling. Instead, the critical factor is tire (tyre). Teams should carefully plan where to change tires of their cars.

The race is a road race having n checkpoints in the course. Their distances from the start are a₁, a₂, ^... , and a_n (in kilometers). The n -th checkpoint is the goal. At the i -th checkpoint (i < n ), tires of a car can be changed. Of course, a team can choose whether to change or not to change tires at each checkpoint. It takes b seconds to change tires (including overhead for braking and accelerating). There is no time loss at a checkpoint if a team chooses not to change tires.

A car cannot run fast for a while after a tire change, because the temperature of tires is lower than the designed optimum. After running long without any tire changes, on the other hand, a car cannot run fast because worn tires cannot grip the road surface well. The time to run an interval of one kilometer from x to x + 1 is given by the following expression (in seconds). Here x is a nonnegative integer denoting the distance (in kilometers) from the latest checkpoint where tires are changed (or the start). r , v , e and f are given constants.

1/(v - e x (x - r))        (if xr)

1/(v - f x (r - x))        (if x < r)

Your mission is to write a program to determine the best strategy of tire changes which minimizes the total time to the goal.

Input 

The input consists of multiple datasets each corresponding to a race situation. The format of a dataset is as follows.

n

a₁ a₂...a_n

b

r v e f

The meaning of each of the input items is given in the problem statement. If an input line contains two or more input items, they are separated by a space.

n is a p ositive integer not exceeding 100. Each of a₁, a₂, ^... , and a_n is a positive integer satisfying 0 < a₁ < a₂ <...< a_n10000 . b is a positive decimal fraction not exceeding 100.0. r is a nonnegative integer satisfying 0ra_n - 1 . Each of v, e and f is a positive decimal fraction. You can assume that v - e x (a_n -1 - r)0.01 and v - f x r0.01 .

The end of the input is indicated by a line with a single zero.

Output 

For each dataset in the input, one line containing a decimal fraction should b e output. The decimal fraction should give the elapsed time at the goal (in seconds) when the best strategy is taken. An output line should not contain extra characters such as spaces.

The answer should not have an error greater than 0.001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.

Sample Input 

2 
2 3 
1.0 
1 1.0 0.1 0.3 
5 
5 10 15 20 25 
0.15 
1 1.0 0.04 0.5 
10 
1783 3640 3991 4623 5465 5481 6369 6533 6865 8425 
4.172 
72 59.4705 0.0052834 0.0611224 
0

Sample Output 

3.5397 
31.9249 
168.6682

---

題目描述：

方程式賽車要跑完整個賽程，而每個輪胎都有其磨損產生的效應，題目給定每增加跑的單位 1，
則相對應時間需要多少的關係式，而如果中途換新的輪胎，則需要額外花 b 秒裝置。

問跑完全程的最少時間。

題目解法：

先將跑的距離所需要時間計算出來，之後窮舉每個新輪胎跑了多遠進行轉換。

#include <stdio.h>
#include <algorithm>
using namespace std;
int a[105];
double dp[105];
double time[10005];
int main() {
    int n;
    int i, j, k;
    double b, r, v, e, f;
    while(scanf("%d", &n) == 1 && n) {
        dp[0] = 0, a[0] = 0;
        time[0] = 0;
        for(i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            dp[i] = 1e+30;
        }
        scanf("%lf", &b);
        scanf("%lf %lf %lf %lf", &r, &v, &e, &f);
        for(i = 1; i <= a[n]; i++) {
            if(i-1 < r)
                time[i] = time[i-1]+ 1.0/(v-f*(r-(i-1)));
            else
                time[i] = time[i-1]+ 1.0/(v-e*((i-1)-r));
        }
        for(i = 0; i <= n; i++) {
            for(j = i+1; j <= n; j++)
                dp[j] = min(dp[j], dp[i]+b+time[a[j]-a[i]]);
        }
        printf("%.4lf\n", dp[n]-b);
    }
    return 0;
}