Dynamic programming

Moderator: Board moderators

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

Dynamic programming

Look at this address: http://cepc.mimuw.edu.pl/pages/problems.htmlthere are problems which was in Central European Programming Contest.
Especially at problem H Voracious steve. This problem may be solved by
usage dynamic programming. But I don't understand the IDEA of this. If anybody may explain it to me I will be very happy. Thanks in advance.

ps: Look at problems on this site http://cepc.mimuw.edu.pl/ they are very interesting and very HARD to solve.

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

I am one of the authors of this task so I can give you a hint. Let us presume, that we have an array , that x element of it tell us how many cookies the person who starts will eat if the number of cookies is x. So our answer is the value from index n, we read from the input.

Now about finding these values. We use simply dynamic programming. ( we have counted all the smaller indexes before). So the time complexity is O(n*n*k), while O(n*k) is time needed for single dynamic programming.

Good Luck

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

Is my assumption correct?

If I know how many cookies eat the first player when game starts with X cookies for some X = 0,1,2,...,x and I must count how many cookies will 1st player can eat if he starts and game starts with X+1 cookies, may I progress like this I will try to get all M = 1,2,...,m and i will get max of the second player may get + m. Or something like this?

Is my assumption correct.

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

I make some program, but it is ot an optimal strategy

my program is this:
[cpp]
int M[102];

int m, n;
int main() {
scanf("%i%i", &n, &m);

for (int p=0; p<=n; p++) {
T[p] = -1;
M[0] = 0;
if (p <=m) {
M[p] = p;
continue;
}
for (int i=1; i<=m; i++) {
if (m + M[p-m] > M[p]) M[p] = m + M[p-m];
}
}

}

[/cpp]

If somebody can me give a hint to solve it I will be like.