Sicily 1057. Rhyme Schemes (贝尔数+高精度)

题目：http://soj.me/1057

思路：这题求的是贝尔数 http://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%95%B0

用以下方法建构一个三角矩阵（形式类似）：

• 第一行第一项是1（a_{1,1} = 1）
• 对于n>1，第n行第一项等同第n-1行最后一项。（
• 对于m,n>1，第n行第m项等于它左边和左上方的两个数之和。（

然后因为上限是50 输出的数超大 所以用数组存

不想开三位数组，就用string写了个高精度的加法；

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
string arr[55][55];


string add(string num1,string num2)
{
    int len1=num1.size();
    int len2=num2.size();
    string num3;
    reverse(num1.begin(),num1.end());
    reverse(num2.begin(),num2.end());
    int flag=0;
    for (int i = 0; i < max(len1,len2); i++)
    {
        if(i<min(len1,len2))
        {
            int t;
            t=num1[i]-'0'+num2[i]-'0'+flag;
            flag=t/10;
            num3+='0'+t%10;
        }
        else
        {
            int t;
            if(len1>len2)
            {
                t=num1[i]+flag-'0';
                flag=t/10;
                num3+='0'+t%10;
            }
            else 
            {
                t=num2[i]+flag-'0';
                flag=t/10;
                num3+='0'+t%10;
            }
        }
    }
    if(flag) num3+='1';
    reverse(num3.begin(),num3.end());

    return num3;

}

int main()
{
    while(1)
    {
        int n;
        cin>>n;
        if(n==0) break;
        
        arr[1][1]="1";

        for(int i=2;i<=n;i++)
        {
            arr[i][1]=arr[i-1][i-1];
            for(int j=2;j<=i;j++)
            {
                arr[i][j]=add(arr[i-1][j-1],arr[i][j-1]);
            }
        }
    cout<<n<<" "<<arr[n][n]<<endl;
    }

    return 0;

}