Dynamic Programming Type

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Dynamic Programming (DP) :

1. Classic Dynamic Programming
a. LCS
   Problem: 1. SAMER08D

b. LIS
   Problem: 1. Beautiful People
                 2. MDOLLS
                 3. MSTICK
                 4. MCARDS

c. Edit Distance

d. Matrix Chain Multiplication
   Problem: 1. Mixtures

e. Knapsack
   Problem: 1. Scubadiv

2. Advance DP
a. DP k-th lexicographical string

Problem: 1. z-01 paths

                   2. z-board
                   3. Linear Garden (IOI 2008)

b. DP tree
    Problem: 1. z-sumpaths
                   2. River (IOI 2005)
                   3. z-company
                   4. Greedy Hydra (CNOI 2002)
                   5. VOCV
                   6. PT07F
                   7. PT07X
                   8. nagibni

c. DP+ BIT/segment tree
    Problem: 1. Salesman (IOI 2009)
                   2. explosion
                   3. intervali
                   4. RENT
                   5. INCSEQ
                   6. INCDSEQ

d. DP+ convex hull
    Problem: 1. Batch Scheduling (IOI 2002)
                   2. NKLEAVES
                   3. Harbingers (CEOI 2009)
                   4. Commando (APIO 2010)

e. DP pre-processing
    Problem: 1. Oil (APIO 2009)
                   2. Garden (IOI 2005)
                   3. Pyramid (IOI 2006)

f. DP bitmask
   Problem: 1. Reklame
                  2. Chess
                  3. Bond
                  4. TRSTAGE
                  5. HIST2
                  6. LAZYCOWS

g. Problem 1: Grid (BOI 2008)

h. DP matrix multiplication/ DP using recurrence
    Problem 1. SEQ
                  2. SPP
                  3. z-funkcija
                  4. mit-indiv09-words
                  5. Reading (Balkan 2009)
                  6. Super Climber
                  7. z-mario

i. DP+ trie
   Problem 1. MORSE

j. DP+geometry
   Problem 1. MPOLY
                 2. CVXPOLY
                 3. MTRIAREA

k. DP + Binary Search

Problem 1. Game (IOI 2008, Practice session)

l. DP + Knuth Optimization
   Problem 1. Breaking Strings
Other Problems in SPOJ can be found here by pt1989
Thanks to pt1989

Here are problems in acm.sgu.ru 269, 273, 304, 317, 356, 396, 445, 447, 458, 489, 494
Thanks to natalia

Reference:
      1. Topcoder
      2. Codechef

Комментарии (68)

Показать архивные | Написать комментарий?

Harta

15 лет назад, # |

any feedbacks are welcomed

→ Ответить

Salat

Awesome!

Some others are recommended by Amtrix

vdmedragon

DP using recurrence:
http://www.spoj.pl/problems/SEQ/

http://www.spoj.pl/problems/SPP/

Can I save ur link into my blog?

15 лет назад, # ^ |

Sure

LIS: MDOLLS, MSTICK (SPOJ)

DP + BIT/Segment tree: INCSEQ,INCDSEQ, RENT (SPOJ), Intervalli (z-trenning).

BIT: HELPBOB, HIST2 (SPOJ)

I think HIST2 suits to DP+bitmask

DP+geometry: MPOLY, CVXPOLY,MTRIAREA (SPOJ)

some more : http://pt1989.22web.net/c0ding/spoj.php?search=dp (thanks to Pratik)

Added thx

cmd	15 лет назад, # \| 0 LIS: http://acm.sgu.ru/problem.php?contest=0&problem=199 → Ответить

Thx ^^

zillion thanks to all contributors

wbdyni344

Thanks.

baukaman

14 лет назад, # |

Great!

something about graph theory ?

simp1eton

Hi,

It seems that you added the problem NKLEAVES on ztrening. Can I know where you got the testcases from? I got 2 cases wrong (testcase 3 and 8) and I cannot figure out why :(.

14 лет назад, # ^ |

I have sent you a message.

natalia

some DP problems from acm.sgu.ru: 269, 273, 304, 317, 356, 396, 445, 447, 458, 489, 494

Thank you so much :)

ridowan007

I Love DP :)
Thanks for it

can someone suggest some game problems solved using DP? thx

Try this one. It is a problem that I came across in the past. Sorry, I forgot the website and don't have the testcases :(, but I know the algorithm though XD.

You have a N bowling pins (1<=N<=1000) arranged in a line. The pins are represented as a string of 1s and 0s. 1 means the pin is still standing and 0 means the pin has been knocked down. Player A and B take turns to play this game, with player A moving first.

In each of their turns, A or B chooses to knock down up to K (1<=K<=N) consecutive standing pins down. A player can only knock down exactly one consecutive block of standing pins during his turn. He must also knock down at least 1 pin. The player who cannot make a move loses.

Given N,K, and the initial starting configuration of the pins, determine who will win under optimal play. If A will win, output the resulting configuration of the pins after A has made his move. If there are multiple moves A can make, output the move that will result in a lexicographically smallest resulting formation.

Note: You do require a bit of game theory before you can solve this problem.

ow.. thx for the problem, I just notice that someone had replied xD

bhardwajjayesh7

hi,
I am facing problems with the chess problem listed above. Can anyone suggest some hints to solving the problem.

P.S: I am a newbie in DP

since M is small (M<=10) you can use bitmask.
0->no king
1->there is a king
dp[i][state] where state means the state of the kings in row-i
you can add dp[i][state1] with dp[i-1][state2] if kings in state2 can't attack kings in state1.

EmadWilliam

DP + Binary Search

(Game, IOI 2008, Practice session)

added. Thx

CherryTree

dp+bin. search: z-McZ
knapsack: FARMER
k-th lexicographical string: LEXBRAC
dp pre-processing: MSE06H

a70babat

hi,
can you say some hints for problem MTRAREA? is there any solution better than O(n^2)?

it4.kp

You can solve it in O(n*log(n)). First find a convex hull, and then use the method described here.

thanks. beautiful idea! I was trying to solve it using DP. does it have any efficient solution using DP?

Mehrdad

hi,
What is DP + Knuth Optimization?

Hopefully this will help :)

Thanks

fataluk1

Anyone got a clue on how to approach The Greedy Hydra problem? It seems tough :|

If the number of colours >= 3, you can always colour the edges in such a way that no fruits are eaten. Just alternate the colouring.

If the number of colours == 2, then you write the N^3 dp.

iscsi

13 лет назад, # |

Hi

Can anybody help me what is the problem with my solution for the mixtures problem? (I've got WA)

(I've checked spoj forum and my solution is correct those test case.. :( )

Oleg	13 лет назад, # ^ \| +1 Seems it won't even pass example input. There can be multiple input in single file - you read only first one. → Ответить

13 лет назад, # ^ |

Thank you, it's a shame :( I was careless sry..

naggar

That was my bug too, Hi 5 ! LOL :D

f.nasim

Also mine. :)

Inf_Zero

Is there something wrong with z-trening!!!!
please provide some alternative(judge) for the z-trening problems in above list

keivan

12 лет назад, # ^ |

I have the same problem .

sergio3010

same problem here.

Nourin_Eka

12 лет назад, # |

Hello,

Any useful link,tutorial to get idea about Digit DP?

To solve problem like those here:

http://www.lightoj.com/volume_showproblem.php?problem=1122

http://www.lightoj.com/volume_showproblem.php?problem=1125

THanks :)

Shafaet

I don't know what you meant by "digit dp" but these are very simple dp problems. For example in "1122 — Digit Count" your state can be (number of digits taken so far, last digit taken), now you can just add new numbers if it is valid, go to next state and add the answers.

shakil

For the problem 1125, your DP should have three states like [current position of the array][how many left to take][remainder of the sums of the chosen elements].

suppose you are in a state like this [25][2][5]

then you can either

1. take the 25th element and add it to remainder and mod it which will take you to the state [26][1][ (5+X[25] + mod)%mod ]

2. or you can skip it and go to the next state which will be then [26][2][5]

By this way you can figure out all the possible combinations.

Here is my source code -->

Mr.Awesome

9 лет назад, # ^ |

← Rev. 2 →

In your code you did something like this ((mod+arr[pos])%d) +d )%d why ??

isn't this enough (mod+arr[pos])%d because x%d always >=0 , right ??

UDP : i got it , numbers can be negative , that's why .

Robert

Awesome!!!!!!

charlie

11 лет назад, # |

why the links to problems not found? who can helpme? I need try resolve many exercise of DP... sorry for my english...

cup_of_tea

11 лет назад, # ^ |

This post is 3 years old, and hasn't been updated since a moment. So it isn't surprising that some links doesn't exist anymore. After a little search on google, it seems that "z-trening" can't be found. But for the links who reference to a problem on spoj/codeforces/topcoder, there must be no problem.