ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1017. Staircases

Do you know a faster algorithm?
Posted by lql1993 23 Oct 2008 19:18
I used dp and this is my program:
var f:array[0..500,0..500]of extended;
    i,j,n:longint;
function min(a,b:longint):longint;
 begin
  if a<b then exit(a);
  exit(b);
 end;
begin
 readln(n);
 fillchar(f,sizeof(f),0);
 f[0,0]:=1;
 for i:=1 to n do
  for j:=1 to i do
   f[i,j]:=f[i,j-1]+f[i-j,min(j-1,i-j)];
 writeln(f[n,n]:0:0);
end.

But I want to know a faster algorithm,
could you please tell me?
Re: Do you know a faster algorithm?
Posted by Antagonism 1 Feb 2011 15:10
let us suppose this is a building.
T[i][j] is the total number of buildings which uses i bricks, and its ground floor is exactly j.
O(n*logn).
AC code.
#include<iostream>
using namespace std;
__int64 T[501][35];
__int64 sum;
int n;
inline __int64 max(__int64 i,__int64 j)
{
    return i>j?i:j;
}
int main()
{
    int i,j,k;
    scanf("%d",&n);
    T[1][1]=1;
    for(i=2;i<=n;i++)
    {
        for(j=1;((j*(j+1))>>1)<=i;j++)
        {
            T[i][j]=T[i-j][j]+T[i-j][j-1];
        }
    }
    for(j=1;((j*(j+1))>>1)<=n;j++)
    {
        sum+=T[n][j];
    }
    printf("%I64d\n",sum-1);
    return 0;
}
Re: Do you know a faster algorithm?
Posted by Antagonism 1 Feb 2011 15:20
sorry it's O(n^3/2)