Discussion @ 1776. Anniversary Firework @ Timus Online Judge

help wa6

Posted by Ibragim Atadjanov (Tashkent U of IT) 22 Oct 2010 12:28

I used dp with two params.
dp[n][k] =(sum(i=0..n-1)max(dp[i][k+1], dp[n-i-1][k+1]))/n
k is number of salvos

ans =10 * dp[n][1];

Edited by author 23.10.2010 02:29

Re: help wa6

Posted by Oleg Strekalovsky [Vologda SPU] 22 Oct 2010 18:57

Ibragim Atadjanov (Tashkent U of IT) wrote 22 October 2010 12:28

I used dp with two params.
dp[n][k] =(sum(i=0..n-1)max(dp[i][k+1], dp[n-i-1][k+1]))/n
number of salvos

ans =10 * dp[n][1];

Nice.
What about initialisation values for array dp, interval for k, and solution explanation?

Re: help wa6

Posted by Ibragim Atadjanov (Tashkent U of IT) 23 Oct 2010 02:18

initial params is as follows
read n then n = n - 2;
dp[0][k] = 0 {k = 1..n}
dp[1][k] = k {k = 1..n}
k is salvo number

Edited by author 23.10.2010 02:29

Discussion of Problem 1776. Anniversary Firework