ural 1017. Staircases

http://acm.timus.ru/problem.aspx?space=1&num=1017

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 600
 5 using namespace std;
 6 
 7 __int64 dp[maxn][maxn];
 8 
 9 int main()
10 {
11     int n;
12     scanf("%d",&n);
13     memset(dp,0,sizeof(dp));
14     dp[1][1]=1;
15     for(int i=2; i<=n; i++)
16     {
17         for(int j=1; j<=i; j++)
18             dp[i][j]=dp[i-1][j-1]+dp[i-j][j-1];
19     }
20     __int64 sum=0;
21     for(int i=0; i!=n; i++) sum+=dp[n][i];
22     printf("%I64d
",sum);
23     return 0;
24 }

View Code