Discussion @ 1776. Anniversary Firework @ Timus Online Judge

BORODA give me a hint, please... [3] // Problem 1776. Anniversary Firework 31 Jan 2014 23:16

I tried to solve it with (dp[i] = sum_j(max(dp[j - 1], dp[i - j])) + 10) formula, but the way of getting the math expectation as max(dp[A], dp[B]) isn't right. Ho to do it? What is the formula..?

please, help me... :(

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: give me a hint, please... [2] // Problem 1776. Anniversary Firework 1 Feb 2014 03:13

Add one more dimension to your DP

BORODA Re: give me a hint, please... [1] // Problem 1776. Anniversary Firework 2 Feb 2014 00:11

oough, I still cant get it. What is the 2nd dimension? I divide the current line(C) to A and B... I really cant understand what else should I know or do to calc C.

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: give me a hint, please... // Problem 1776. Anniversary Firework 2 Feb 2014 04:02

What else? You should actually know what is max you're trying to find expectation of!

Discussion of Problem 1776. Anniversary Firework