Dynamic Programming: Two Parameters


Plus
Pin


Problem description Progress
ID 18786. Pascal's triangle
Темы: Dynamic Programming: Two Parameters   

Pascal's triangle is constructed as follows. The first line consists of a single number equal to one. Each next 
The
contains one number more than the previous one. The first and last of these numbers are equal to 1, and all the rest are calculated as the sum of the number above it in the previous line and the number to the left of it in the previous line.
 
Input: input one number N (\(0<=N< ;=30\)).
 
Output:  output N lines of Pascal's triangle. Separate numbers in a line with a single space.

Note
All numbers in Pascal's triangle under the specified restrictions are included in Longint.
 
 
Examples
# Input Output
1 8
1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1
 

ID 23407. Minimum path in table
Темы: Dynamic Programming: Two Parameters   

In a rectangular table NxM (in each cell of which a certain number is written), at the beginning the player is in the upper left cell.
In one move, he is allowed to move to the next cell either to the right or down (it is forbidden to move to the left and up).
When passing through a cell, the player is charged as much c.u.
 
It is required to find the minimum amount of c.u., by paying which the player can get to the lower right corner.
 
Input:
- the first line contains two numbers N and M - table sizes (\(1<=N<=20 \), \(1<=M<=20\));
- then there are N lines of M numbers in each - sizes of fines in c.u. for passing through the corresponding cells (each number from 0 to 100).
 
Output: print the minimum amount you can spend to get in the lower right corner.
 
 
Examples
# Input Output
1
3 4
1 1 1 1
5 2 2 100
9 4 2 1
8

ID 23412. Parentheses recovery
Темы: Dynamic Programming: Two Parameters   

A pattern is specified, consisting of parentheses and question marks. You need to determine how many ways you can replace question marks with parentheses so that you get a correct bracket expression.
 
Input: Enter a string that contains the given pattern with a maximum length of 80 characters.
 
Output: print the desired number of ways. The initial data will be such that this number does not exceed \( 2 \cdot 10^9\).
 
 
Examples
# Input Output
1 ????(? 2
 

ID 33142. Knight's move_1
Темы: Dynamic programming    Dynamic Programming: Two Parameters   

Given a rectangular board N × M (N rows and M columns). In the upper left corner is a chess knight, which must be moved to the lower right corner of the board. In this case, the knight can ONLY move two cells down and one cell to the right, or two cells to the right and one cell down (see picture).
 
 
We need to determine how many different routes there are from the top left to the bottom right corner.
 
Input: the input string contains two natural numbers N and M (\(1 <= N,\ M <= 50\)).  
 
Output: print a single number of ways to get the knight to the bottom right corner of the board.
 
Examples
# Input Output
1 4 4 2

ID 33143. Knight's move - 2
Темы: Dynamic programming    Dynamic Programming: Two Parameters   

Given a rectangular board N × M (N rows and M columns). In the upper left corner is a chess knight, which must be moved to the lower right corner of the board. In this case, the horse can only walk as shown in the figure:

 
We need to determine how many different routes there are from the top left to the bottom right corner.
 
Input:  the input string contains two natural numbers N and M (< span class="math-tex">\(1 <= N,\ M <= 15\)).  
 
Output: print a single number of ways to get the knight to the bottom right corner of the board.
 
Examples
# Input Output
1 4 4 2
2 7 15 13309

ID 38286. Need more gold
Темы: Dynamic Programming: Two Parameters   

Petya loves computer games very much. Recently, he discovered an interesting role-playing game on the Internet. Controlling the hero, you need to look for magical artifacts and get gold.

Unfortunately, the very first quest in the game put Petya in a dead end. After completing the task, he received n magical artifacts that can be used to get gold. For each artifact its value is known, for the i -th artifact it is equal to wi . Artifacts can be activated to get gold. Each artifact can only be activated once. Petya can activate artifacts in any order.

The hero controlled by Petya has magic power, initially it is equal to zero. There are two ways to activate an artifact: through magic and through force. If you activate an artifact with a value of w using magic, then the hero's magic power is increased by w . If you activate an artifact with a value of w using force, then the hero receives xw gold coins, where x — the hero's magic power at the moment the artifact is activated.

For example, if the hero Petit received 4 artifacts with values ​​1, 1, 2 and 2, then you can get 9 gold coins by proceeding as follows. First, you need to use magic to activate one artifact each with a value of 1 and 2. After that, the hero's magic power is 3, now you can activate the remaining artifacts using strength and get 3 and 6 gold coins, respectively.

Help Petya determine the maximum number of gold coins he can get by activating the artifacts in the correct order in the best possible way.

Input
The first line of the input contains a single number n — number of magic artifacts ( 1 ≤ n ≤ 100 ).

The second line of the input contains n numbers w1 , w2 , ..., wn — artifact values ​​( 1 ≤ wi ≤ 100 ).

Imprint
Print the maximum possible number of gold coins that can be obtained with the help of magical artifacts.

Examples
# Input Output
1 4
1 1 2 2
9

ID 38296. Daily Rewards
Темы: Dynamic Programming: Two Parameters   

Misha installed a new game "Memtest 2k17" on his phone. It provides daily rewards for visiting. Rewards come in n levels. The type of reward depends on the reward for the previous day, namely:

if the player did not visit the game the previous day, then for today's visit he will receive a level 1 reward;
if a player entered the game the previous day and received a level k reward ( k ≠ n ), then for today's visit he will receive a level k reward + 1 ;
if a player entered the game the previous day and received a level n reward, then for today's visit he will receive a level 1 reward.
At the Forum for Cool Programmers, Misha found out that the rewards of each of the levels are respectively a 1 , a 2 , ..., a n gold coins.
In m days, there will be a Memtest 2k17 tournament, for which Misha wants to collect as many gold coins as possible. Help him plan visits to the game during the m days left before the tournament. Find the most gold coins he can get from daily rewards during this period. We can assume that the game was installed on the first of these m days, that is, Misha has never logged into it before.

Input
The first line of the input contains natural numbers n and m ( 1 ≤ n , m ≤ 1000 ) — number of reward levels and days before the tournament.

The second line of the input contains n integers a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 1000 ), where a i — the value of the i-th level reward in gold coins.

Imprint
Print one natural number — the most gold coins that Misha can get before the tournament.

Note
In the first test from the example, it is profitable for Misha to enter the game every day. Then he will get 1 + 2 + 4 = 7 gold coins.

In the second test from the example, it is profitable for Misha to enter the game on the first and third days, receiving 4 coins on each of them, then he will receive 8 coins in total.
 

Examples
# Input Output
1 3 3
1 2 4
7
2 3 3
4 2 1
8

ID 38515. Burgers at McDuck's
Темы: Dynamic programming    Dynamic Programming: Two Parameters   

The popular fast food chain «McDuck's» opened a new branch in Berland. The restaurant has k stoves. To cook a burger, you need to fry a patty for a minute on one of the stoves, so a restaurant can cook no more than k burgers per minute.

It is known that in «McDuck's» n clients will come. The i-th of them will arrive at time ti, order xi burgers and be ready to pay ci burles for them. Each client is ready to wait for an order for w minutes, and if w minutes after arrival he has not received xi burgers, he will not pay anything. At the same time, each client is ready to receive only fresh burgers, that is, only those for which the burgers were fried not earlier than the time ti. Due to such complex requirements, the restaurant will not always be able to fulfill all the orders of all customers.

The restaurant managers were interested in the maximum profit McDuck's could make. Help them answer this difficult question. We can assume that no money is spent on cooking burgers.

Input
The first line contains three integers n, k and w (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10, 1 ≤ w ≤ 60) — the number of clients, the number of plates and the waiting time for the client, respectively.

The next n lines contain descriptions of clients, consisting of three integers — ti, xi, ci (1 ≤ ti, xi sub>, ci ≤ 109) — the time (in minutes) of arrival of the i-th customer, the number of burgers he will order and the number of burles he is willing to pay, respectively. Clients are listed in ascending order of arrival time, i.e. for any i > 1 it is true that ti−1 ≤ ti.

Imprint
In a single line print a single number — maximum restaurant profit.

Note
In the first test example, the first patty can be fried at time 0, and then at time 1 it will be ready and can be served in a burger to the first client. At time 1, you can put another patty to fry, it will be ready at time 2 and can be served in a burger to the second client.
 

Examples
# Input Output
1 2 1 1
1 1 5
1 1 7
12
2 3 2 2
1 6 8
2 5 10
3 4 4
12

ID 40064. Sequences of length N
Темы: Dynamic Programming: Two Parameters   

How many integer sequences of length N, A = (A1,…,AN), satisfy all given below conditions?
1) 1 <= Ai <= M (1 <= i <= N)
2)\(\sum\limits_{i=1}^NA_i \le K\)

Input
The input is a string containing three integers N, M (1 <= N, M <= 50), K (N <= K <= NM).

Imprint
Output the answer to the problem.
 

Examples
# Input Output Explanations
1
2 3 4
6
(1,1) (1,2) (1,3) (2,1) (2,2) (3,1)