Ural 1017. Staircases

1017. Staircases

Time Limit: 1.0 second
Memory Limit: 16 MB

One curious child has a set of N little bricks (5 ≤ N ≤ 500). From these bricks he builds different staircases. Staircase consists of steps of different sizes in a strictly descending order. It is not allowed for staircase to have steps equal sizes. Every staircase consists of at least two steps and each step contains at least one brick. Picture gives examples of staircase for N=11 and N=5:

Your task is to write a program that reads the number N and writes the only number Q — amount of different staircases that can be built from exactly N bricks.
Input
Number N
Output
Number Q
Sample
input output
212

995645335


题目大意：给你N块砖，一共有多少种方法使得分成几叠且每叠的砖的数量均不同，且叠数不能少于2。这题实质上一个整数划分问题。如N=6时，

6 = 1 + 2 + 3

6 = 1 + 5

6 = 2 + 4

一共有3种方法！

算法分析：设f[n][k]表示将数n分成k份一共的分法。则按照最小的那一份分类有：

如果最小的为1，则f[n][k]=f[n-k][k-1];

如果最小的不为1，则f[n][k]=f[n-k][k];

从而f[n][k]=f[n-k][k-1]+f[n-k][k],且有当k*(k+1)/2>n时f[n][k]=0；当k=1时f[n][k]=1。要求的答案即为：f[n][max_k]+f[n][max_k-1]+……+f[n][2].

#include <iostream>
#include <memory.h>
using namespace std;
const int maxn=510;
typedef long long lld;
lld f[maxn][maxn];
lld dp(lld n,lld k)
{
    if(k==1)    return f[n][k]=1;
    if(f[n][k]!=-1)     return f[n][k];
    if((1+k)*k>2*n)     return f[n][k]=0;
    lld sum=dp(n-k,k-1)+dp(n-k,k);
    return f[n][k]=sum;
}
int main()
{
    memset(f,-1,sizeof(f));
    lld n;
    cin>>n;
    lld sum=0;
    for(int i=n;i>=2;i--)
    {
        sum+=dp(n,i);
    }
    cout<<sum<<endl;
    return 0;
}