|
|
back to boardprogram staircases;
var a:array[0..500] of extended;
n,i,j:longint;
begin
read(n);
fillchar(a,sizeof(a),0); a[0]:=1;
for j:=1 to n do
for i:=n downto j do a[i]:=a[i]+a[i-j];
a[n]:=a[n]-1;
writeLn(a[n]:0:0);
end. pls explain ur algorithm i.e. write down recurrent equation that it
use ... email me: oberon at verba.com.ua What does F(n) mean in your programme? Thank Nickolas.
I didn't see his carefully, just a look. To my surprise it is so short. Suddenly I found a good way to solve this problem -- When I got AC , I found it looks like his one very much...
We can get f(m,n) = f(m,n-1) + f(m-n,n-1) easily
(Sorry my English isn't good enough to explain what m & n are.)
Notice that f(...,n) is based on f(...,n-1)
Then, we can get a good program.
Time : O(n^2)
Memory : O(n)
Thanks! Oh,that is easy to understand!
In fact,it's multinomial multiplication,and I think it's just (1+x)*(1+x^2)*(1+x^3)...... Is that right? I solved this problem another way... But your program is perfect... can you explain how did you invent it? My solution is fast! valery@uni.lg.ua
Edited by author 03.04.2005 04:15 |
|
|
