条形图

题目描述

小虎刚则上了幼儿园，老师让他做一个家庭作业：首先画3行格子，第一行有3个格子，第二行有2个格子，第三行有1个格子。每行的格子从左到右可以放棋子，但要求除第一行外，每行放的棋子数不能超过上一行的棋子。玩了一会，小虎问哥哥大虎：这个作业有很多种摆放法，我想都找到，但我不知道有多少种方案，你能帮助我吗？

大虎是学校信息学集训队的，立刻想到用计算机来解决这个问题，并很快有了解答：13。第2天他把问题拿到学校，并说如果第一行有N个格子，第二行有N－1个格子，...，第N行有1个格子，怎么办？现在请你一块来帮助他解决这个难题。

输入输出格式

输入格式：

仅一行，一个正整数N。

输出格式：

一行，方案总数。

输入输出样例

输入样例一：

2

输出样例一：

4

输入样例二：

3

输出样例二：

13

说明

样例说明：

N＝2时，有如下4种摆放棋子法(×表示棋子，_表示空格)：

×_                                                    
_  

××
_

×_
×

××
×

数据规模：

对于30%的数据：1≤N≤12；

对于50%的数据：1≤N≤30；

对于100%的数据：1≤N≤100。

 

思路：和“摆花”一样，不过要使用高精度加法。

代码：

//程序名:新的C++程序
//作者: 

#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;
int n;
string c[105][105],ans;
string jia(string a,string b)
{
    int len1=a.size(),len2=b.size(),len3=max(len1,len2),f=0;
    string now;
    for(int i=0;i<len3;i++)
    {
        if(i<len1&&i<len2)f=a[i]-'0'+b[i]-'0'+f,now+=f%10+'0',f=f/10;
        else if(i<len1)f=a[i]-'0'+f,now+=f%10+'0',f=f/10;
        else if(i<len2)f=b[i]-'0'+f,now+=f%10+'0',f=f/10;
    }
    if(f)now+=f+'0';
    return now;
}
string dao(string s)
{
    for(int i=0;i<s.size()/2;i++)swap(s[i],s[s.size()-1-i]);
    return s;
}
void dfs(int s)
{
    if(s==n+1)return;
    for(register int j=0;j<=s;j++)
    {
        c[s][j]="0";
        for(register int k=0;k<=min(s-1,j);k++)c[s][j]=jia(c[s][j],c[s-1][k]);
    }
    dfs(s+1);
}
int main()
{
    cin>>n;
    c[1][0]="1";c[1][1]="1";
    dfs(2);
    for(register int i=1;i<=n;i++)ans=jia(ans,c[n][i]);
    cout<<dao(ans);

    return 0;
}