条形图(diagrams)

时间：2023-03-10 01:57:10
条形图(diagrams)

条形图(diagrams)

题目描述

小 虎刚上了幼儿园，老师让他做一个家庭作业：首先画3行格子，第一行有3个格子，第二行有2个格子，第三行有3个格子。每行的格子从左到右可以放棋子，但要 求除第一行外，每行放的棋子数不能超过上一行的棋子数。玩了一会，小虎问哥哥大虎：这个作业有很多种摆放法，我想都找到，但我不知道有多少种方案，你能帮 助我吗？
大虎是学校信息学集训队的，立刻想到用计算机来解决这个问题，并很快有了解答：13。第2天，他把问题拿到学校，并说如果第一行有n个格子，第二行有n-1个格子，……，第n行有1个格子，怎么办？现在请你一块来帮助他解决这个难题。

输入

仅1行，一个正整数n。
30%数据：1≤n≤12;
50%数据：1≤n≤30;
100%数据：1≤n≤100。

输出

1行，方案总数。

样例输入

2

样例输出

4

提示

样例解释

四种摆法如下（*表示棋子_表示空格）：

*_                      *_                      **                      **

_                       *                       _                       *

分析：

dp[i][j]表示当第i行(i个格子)有j个棋子的总情况，则dp[i][j]=Σ(dp[i-1][0],dp[i-1][1]...dp[i-1][j/2]);

　　注意：最前面一行（第n行）必须放棋子；本题会爆long long，需要字符串处理；

代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <list>

#include <ext/rope>

#define rep(i,m,n) for(i=m;i<=n;i++)

#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)

#define vi vector<int>

#define pii pair<int,int>

#define mod 1000000007

#define inf 0x3f3f3f3f

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define pi acos(-1.0)

const int maxn=2e5+;

const int dis[][]={{,},{-,},{,-},{,}};

using namespace std;

using namespace __gnu_cxx;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}

int n,m;

string dp[][],ans;

string work(string a,string b)

{

    int len1=a.length(),len2=b.length(),ma=max(len1,len2),cnt=,i;

    string now;

    for(i=;i<ma;i++)

    {

        if(i<len1&&i<len2)

        {

            cnt=a[i]-''+b[i]-''+cnt;

            now+=cnt%+'';

            cnt=cnt/;

        }

        else if(i<len1)

        {

            cnt=a[i]-''+cnt;

            now+=cnt%+'';

            cnt=cnt/;

        }

        else if(i<len2)

        {

            cnt=b[i]-''+cnt;

            now+=cnt%+'';

            cnt=cnt/;

        }

    }

    if(cnt)now+=cnt+'';

    return now;

}

int main()

{

    int i,j,k,t;

    ans="";

    dp[][]=dp[][]="";

    for(int i=;i<=;i++)

        for(int j=;j<=i;j++){

        dp[i][j]="";

        for(int k=;k<=j&&k<=i-;k++)

        dp[i][j]=work(dp[i][j],dp[i-][k]);

        }

    scanf("%d",&n);

    rep(i,,n)ans=work(ans,dp[n][i]);

    reverse(ans.begin(),ans.end());

    cout<<ans<<endl;

    //system ("pause");

    return ;

}

相关文章