ACM学习历程—HDU1028 Ignatius and the Princess（组合数学）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define inf 0x3fffffff

using namespace std;

int a[125][125];

int main()
{
    //freopen ("test.txt", "r", stdin);
    memset (a, 0, sizeof(a));
    for (int i = 1; i <= 120; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            if (i == 1 || i == j)
            {
                a[i][j] = 1;
            }
            else
            {
                for (int k = 1; k <= j && k <= i-j; ++k)
                {
                    a[i][j] += a[i-j][k];
                }
            }
            a[i][0] += a[i][j];
        }
    }
    int n;
    while(scanf("%d", &n) != EOF)
    {
        printf ("%d\n", a[n][0]);
    }
    return 0;
}