Problem Description

Mr. M is an undergraduate student of FDU. He finds an intern position in Beijing, so that He always attend all the college activities. But in the conditions, He must back to Shanghai on certain date. We can assume the important activities that Mr. M must attend all occupy a whole day. Mr. M must take flight to Shanghai before that day and leave after that day, on the other hand, Mr. M is absent in Beijing and He will lose his salary for his absent.
At the cost of flight is much who the loss of salary, so to save the cost on the travel, Mr. M can stay in Shanghai to wait for another important date before he back to Beijing.
Now, Mr. M knows all of the important date in the next year. Help question the schedule his travel to optimize the cost.




Input

The input contains several test cases. The first line of single integer are The number of test cases.
For each test case, the first line contains three integers: n, a and b, denoting the number of important events, the cost of a single flight from Beijing to Shanghai or Shanghai to Beijing and the salary For a single day stay in Beijing. (1 & lt;=n & lt;=100000, 1 & lt;=a & lt;=1000000000, 1 & lt;=b & lt;
=100)The Next line contains n integers ti, denoting the time of the important events. You can assume the ti are in increasing order and they are the company from each other. (0 & lt;=ti & lt;
=10000000)



The Output

For each test case, output a single integer indicating the minimum cost For this year.




The Sample Input



2

1 10 10

5

5 to 10 2

5 to 10 to 15, 65, 70




The Sample Output



Case # 1:30

Case # 2:74

# include
using namespace std;
Int main () {
Int t, d=1, m=1;
Cin> t;
While (t -) {
Int n, a, b, I, c=0, d1, d2.
Cin> N> A> b;
Int a w [100000];
for(i=0; iCin> W [I];
C + a + b=2 *;
for(i=0; iD1=[I + 1) - (w w [I]) * b;
D2=2 * a + b;
If (d1 & gt;=d2)
C +=d2;
The else
C +=d1;
}
Cout<" Case # "& lt; }
}


Turn it in in the wa, don't know where is wrong, or considering the less, hope bosses give advice or comments

CodePudding user response:

This problem is not so simple that need permutation and combination, seeking the optimal solution from these combinations,
Such as an important days can choose to return to Beijing or stay in Shanghai (2) choice, the choice to return the ticket money, choose to leave will deduct wages, every important day you have two choices, each choice to form a composite, calculate the cost of the portfolio, from the cost of these kind of minimum cost,

CodePudding user response:

reference 1st floor qybao response:

this problem is not so simple that need permutation and combination, seeking the optimal solution from these combinations,
Such as an important days can choose to return to Beijing or stay in Shanghai (2) choice, the choice to return the ticket money, choose to leave will deduct wages, every important day you have two choices, each choice to form a composite, calculate the cost of the portfolio, from these kind of find the minimum cost, cost

Between two important day for only 2 kinds of solutions, choose low cost line, because the big day is a must in Shanghai, need not permutation and combination