|
|
back to board<font color="#BA0018">Another idea</font> Posted by sylap 2 May 2013 19:14 My idea is : (a bit complicated) definition : dp[x][0][0] = [...] , x , x-1 , [...] dp[x][0][0] = [...] , x-1 , x-1 , [...] dp[x][1][0] = [...] , x , x-1 dp[x][1][0] = [...] , x-1 , x dp[x][1][0] = [...] , x-2 , x (dp[x][i][j] is number of sequences satisfying the corresponding rule) recurrence : dp[i][0][0] = dp[i-1][0][1]; dp[i][0][1] = dp[i-1][0][0] + dp[i-1][1][0]; dp[i][1][0] = dp[i-1][1][1]; dp[i][1][1] = dp[i-1][1][1] + dp[i-1][1][2]; dp[i][1][2] = dp[i-1][1][0]; answer (to be printed is) : dp[n][0][0] + dp[n][0][1] + dp[n][1][0] + dp[n][1][1] + dp[n][1][2] proof : left for you :) Edited by author 02.05.2013 19:18 Re: <font color="#BA0018">Another idea</font> Posted by neko13 12 Aug 2013 17:24 I have observed the answers.I found that a[i]=a[i-1]+a[i-2]-a[i-5]; I still don't know why! Re: <font color="#BA0018">Another idea</font> Posted by mjolner 13 Aug 2013 21:37 Above has been shown: a[i] = a[i-1] + a[i-3] + 1 this holds for each i, then also: a[i-2] = a[i-3] + a[i-5] + 1 So a[i-2] - a[i-3] - a[i-5] = 1 and (substitute this result in the first equation) a[i] = a[i-1] + a[i-3] + a[i-2] - a[i-3] - a[i-5] which reduces to a[i] = a[i-1] + a[i-2] - a[i-5] Re: How to slove it?? Any hints? I use dfs to find the regular for some test n = 1 2 3 4 5 6 7 8 9 10 11 ans= 1 2 2 4 6 9 14 21 31 46 68 then I found f[n] = f[n-1] + f[n-2] - f[n-5] then I got AC. Re: How to slove it?? Any hints? cool, note that we can unite 3rd and 4th cases as one case when n >= 4. |
|
|