Обсуждение @ 1776. Праздничный фейерверк @ Timus Online Judge

help wa6

Послано Ibragim Atadjanov (Tashkent U of IT) 22 окт 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

Послано Oleg Strekalovsky [Vologda SPU] 22 окт 2010 18:57

Ibragim Atadjanov (Tashkent U of IT) писал(a) 22 октября 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

Послано Ibragim Atadjanov (Tashkent U of IT) 23 окт 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

Обсуждение задачи 1776. Праздничный фейерверк