uestc-dp专题

described below.

The input instance consists of two lines. The first one contains one positive integer n<=200000 denoting the number of towers. The second line contains n positive integers not larger than 1000000000 separated by single spaces being the heights of the towers. Output

For each test case, your program has to write an output conforming to the format described below. You should output one line containing the length of a longest increasing sequence of consecutive towers, achievable by demolishing some consecutive towers or no tower at all. Sample Input 2 9

5 3 4 9 2 8 6 7 1 7

1 2 3 10 4 5 6 Sample Output 4 6 Source

Source Central 2010-2011

Food Delivery

Time Limit: 2000 ms Memory Limit: 65536 kB

Solved: 36 Tried: 373

Description

When we are focusing on solving problems, we usually prefer to stay in front of computers rather than go out for lunch. At this time, we may call for food delivery.

Suppose there are N people living in a straight street that is just lies on an X-coordinate axis. The ith person's coordinate is Xi meters. And in the street there is a take-out restaurant which has coordinates X meters. One day at lunchtime, each person takes an order from the restaurant at the same time. As a worker in the restaurant, you need to start from the restaurant, send food to the N people, and then come back to the restaurant. Your speed is V meters per minute. You know that the N people have different personal characters; therefore they have different feeling on the time their food arrives. Their feelings are measured by Displeasure Index. At the beginning, the Displeasure Index for each person is 0. When waiting for the food, the ith person will gain Bi Displeasure Index per minute.

If one's Displeasure Index goes too high, he will not buy your food any more. So you need to keep the sum of all people's Displeasure Index as low as possible in order to maximize your income. Your task is to find the minimal sum of Displeasure Index. Input

-1

The first line of the input is a positive integer T (T<=15) which is the number of cases that follow. Each case is started with three integers N ( 1 <= N <= 1000 ), V ( V > 0), X ( X >= 0 ), then N lines followed. Each line contains two integers Xi ( Xi >= 0 ), Bi ( Bi >= 0), which are described above.

You can safely assume that all numbers in the input and output will be less than 2^31 - 1. Output

For each test case please output a single number, which is the minimal sum of Displeasure Index. One test case per line. Sample Input 1 5 1 0 1 1 2 2 3 3 4 4 5 5

Sample Output 55 Source

ZOJ Monthly, February 2011

Free Candies

Time Limit: 10000 ms Memory Limit: 131072 kB

Solved: 56 Tried: 164

Description

Little Bob is playing a game. He wants to win some candies in it - as many as possible. There are 4 piles, each pile contains N candies. Bob is given a basket which can hold at most 5 candies. Each time, he puts a candy at the top of one pile into the basket, and if there're two candies of the same color in it , he can take both of them outside the basket and put them into his own pocket. When the basket is full and there are no two candies of the same color, the gme ends. If the game is played perfectly, the game will end with no candies left in the piles. For example, Bob may play this game like this (N=5):

Note that different numbers indicate different colors; there are 20 kinds of colors numbered 1...20. 'Seems so hard...'Bob got very much puzzled. How many pairs of candies could he take home at most? Input

The input will contain no more than 10 test cases. Each test case begins with a line containing a single integer n (1<=n<=40) representing the height of the piles. In the following n lines, each line contains four integers xi1, xi2, xi3, xi4 (in the range 1...20). Each integer indicates the color of the corresponding candy. The test case containing n=0 will terminate the input, you should not give an answer to this case. Output

Output the number of pairs of candies that the cleverest little child can take home. Print your answer in a single line for each test case. Sample Input 5 1 2 3 4 1 5 6 7 2 3 3 3 4 9 8 6 8 7 2 1 1 1 2 3 4 3 1 2 3 4 5 6 7 8 1 2 3 4 0

Sample Output 8 0 3 Source

OIBH Online Programming Contest #1 Mountain Number

Time Limit: 2000 ms Memory Limit: 65536 kB

Solved: 31 Tried: 179

Description

A Mountain number is defined as continuous digits {D0, D1 ? Dn-1} (D0 > 0 and n >= 3),which exist Dm (0 < m < n - 1) satisfied Di-1 < Di (0 < i <= m) and Di > Di+1 (m <= i < n - 1).Such as 121,12341 and so on.

Now,BlinKer is facing a problem.He wants to calculate the number of mountain numbers in the closed interva [A,B].Could you help him? Input

First line is a integer T ,which means the number of test cases. Each case has two integers A,B (0<=A<=B<2^63) in a single line. Output

For each case,first output\#x: \start from 1),then output a single num which is the answer. Sample Input 3 121 121 100 101 12341 12344 Sample Output Case #1: 1 Case #2: 0

Print Article

Time Limit: 3000 ms Memory Limit: 65536 kB

Solved: 53 Tried: 350

Description

Zero has an old printer that doesn't work well sometimes. As it is antique, he still likes to use it to print articles. But it is too old to work for a long time and it will certainly wear and tear, so Zero uses a cost to evaluate this degree.

One day Zero wants to print an article which has N words, and each word i has a cost Ci to be printed. Also, Zero know that print k words in one line will cost