Dynamic programming

[ahanys]

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]

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.





I hope it will help you..



Good Luck

[ahanys]

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.
Please help

[ahanys]

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.