uestc-dp专题

The Most Wonderful Competition

Time Limit: 1000 ms Memory Limit: 65535 kB

Solved: 130 Tried: 1097

Description

Last week, School of Applied Mathematics held a competition of flying kite, contestants are divided into pairs, and one contestant competes with another in each pair. As we know, different way dividing pairs may bring different splendid level value, which appears as a real numbers. Now Miss Ye wants to know how to divide the competitor in order to attain maximum splendid level. Input

The first line of the input contains one integer T, which indicate the number of test case. For each test case, in the first line there is an integer N (N<=16, N is always an even number) indicating there are N contestants taking part the competition.

In the next N line, each line contains N real numbers. The j-th number in the i-th line is the splendid level value when the i-th contestant and the j-th constant are made in one pair. You can assume the j-th number in the i-th line is equal to the i-th number in the j-th line. Outut

For each case, output the maximum total splendid level value accurate to two digits after the radix point. Sample Input 1 2 0.0 1.0 1.0 0.0 Sample Output 1.00

Cheapest Cost

Time Limit: 10000 ms Memory Limit: 65536 kB

Solved: 54 Tried: 361

Description

baihacker chooses the easy mode and is borned in X star. The lowest temperature of X star is 0 degree and the highest is 1000 degree.

The technology of X star is so advanced that the relation department can predict the temperature of the coming 1000 days. The temperature of each day is independent. When the temperature difference of two consecutive days is larger than K, the people will be ill, so the relation department employ Y company to control the temperature such that no people will be ill for the temperature difference.

The cost of change the temperature S degree of a day is S * S.

When temperature difference of two consecutive days is D, then Y company have to pay A * D for maintaining his honor.

As the CTO of Y company, you are to calculate the cheapest cost. Input

The first line of the input is an integer T which stands for the number of test cases. Then T test cases follow.

The first line of each test case is 3 integers N, K, A seperated by a space. Then N integers seperated by a space in a line to represent the temperatures in the coming n days.

constraints:

A, K is in the range of [0, 1000]. N is in the range of [1, 1000].

The temperature after adjusted can not be below 0 or higher than 1000. T is no more than 150 Output

For each test case, output the cheapest cost in a single line. The cost is defined as the sum of changing the temperator and maintaining their honor. Sample Input 2 1 1 1 1 3 1 10 1 2 3

Sample Output 0

AreYouBusy

Time Limit: 1000 ms Memory Limit: 65536 kB

Solved: 68 Tried: 375

Description Happy New Term!

As having become a junior, xiaoA recognizes that there is not much time for her to AC problems, because there are some other things for her to do, which makes her nearly mad.

What's more, her boss tells her that for some sets of duties, she must choose at least one job to do, but for some sets of things, she can only choose at most one to do, which is meaningless to the boss. And for others, she can do of her will. We just define the things that she can choose as \always willing to do the jobs).So can you choose the best sets of them to give her the maximum

points of happiness and also to be a good junior(which means that she should follow the boss's advice)? Input

There are several test cases, each test case begins with two integers n and T (0<=n,T<=100) , n sets of jobs for you to choose and T minutes for her to do them. Follows are n sets of description, each of which starts with two integers m and s (0

One line for each test case contains the maximum points of happiness we can choose from all jobs .if she can’t finish what her boss want, just output -1 . Sample Input 3 3 2 1 2 5 3 8 2 0 1 0 2 1 3 2 4 3 2 1 1 1 3 4 2 1 2 5 3 8 2 0 1 1 2 8 3 2 4 4 2 1 1 1 1 1 1 0 2 1 5 3

2 0 1 0 2 1 2 0 2 2 1 1 2 0 3 2 2 1 2 1 1 5 2 8 3 2 3 8 4 9 5 10

Sample Output 5 13 -1 -1

Defense Lines

Time Limit: 3000 ms Memory Limit: 65536 kB

Solved: 44 Tried: 342

Description

After the last war devastated your country, you - as the king of the land of Ardenia - decided it was high time to improve the defense of your capital city. A part of your fortification is a line of mage towers, starting near the city and continuing to the northern woods. Your advisors determined that the quality of the defense depended only on one factor: the length of a longest contiguous tower sequence of increasing heights. (They gave you a lengthy explanation, but the only thing you understood was that it had something to do with firing energy bolts at enemy forces). After some hard negotiations, it appeared that building new towers is out of question. Mages of Ardenia have agreed to demolish some of their towers, though. You may demolish arbitrary number of towers, but the mages enforced one condition: these towers have to be consecutive. For example, if the heights of towers were, respectively, 5, 3, 4, 9, 2, 8, 6, 7, 1, then by demolishing towers of heights 9, 2, and 8, the longest increasing sequence of consecutive towers is 3, 4, 6, 7. Input

The input contains several test cases. The first line of the input contains a positive integer Z<=25, denoting the number of test cases. Then Z test cases follow, each conforming to the format