条形图(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

1
2
2

样例输出

复制代码4

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+10; const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}}; using namespace std; using namespace __gnu_cxx; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;} int n,m; string dp[110][110],ans; string work(string a,string b) { int len1=a.length(),len2=b.length(),ma=max(len1,len2),cnt=0,i; string now; for(i=0;i<ma;i++) { if(i<len1&&i<len2) { cnt=a[i]-'0'+b[i]-'0'+cnt; now+=cnt%10+'0'; cnt=cnt/10; } else if(i<len1) { cnt=a[i]-'0'+cnt; now+=cnt%10+'0'; cnt=cnt/10; } else if(i<len2) { cnt=b[i]-'0'+cnt; now+=cnt%10+'0'; cnt=cnt/10; } } if(cnt)now+=cnt+'0'; return now; } int main() { int i,j,k,t; ans="0"; dp[1][0]=dp[1][1]="1"; for(int i=2;i<=100;i++) for(int j=0;j<=i;j++){ dp[i][j]="0"; for(int k=0;k<=j&&k<=i-1;k++) dp[i][j]=work(dp[i][j],dp[i-1][k]); } scanf("%d",&n); rep(i,1,n)ans=work(ans,dp[n][i]); reverse(ans.begin(),ans.end()); cout<<ans<<endl; //system ("pause"); return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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+10;
const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
using namespace std;
using namespace __gnu_cxx;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int n,m;
string dp[110][110],ans;
string work(string a,string b)
{
    int len1=a.length(),len2=b.length(),ma=max(len1,len2),cnt=0,i;
    string now;
    for(i=0;i<ma;i++)
    {
        if(i<len1&&i<len2)
        {
            cnt=a[i]-'0'+b[i]-'0'+cnt;
            now+=cnt%10+'0';
            cnt=cnt/10;
        }
        else if(i<len1)
        {
            cnt=a[i]-'0'+cnt;
            now+=cnt%10+'0';
            cnt=cnt/10;
        }
        else if(i<len2)
        {
            cnt=b[i]-'0'+cnt;
            now+=cnt%10+'0';
            cnt=cnt/10;
        }
    }
    if(cnt)now+=cnt+'0';
    return now;
}
int main()
{
    int i,j,k,t;
    ans="0";
    dp[1][0]=dp[1][1]="1";
    for(int i=2;i<=100;i++)
        for(int j=0;j<=i;j++){
        dp[i][j]="0";
        for(int k=0;k<=j&&k<=i-1;k++)
        dp[i][j]=work(dp[i][j],dp[i-1][k]);
        }
    scanf("%d",&n);
    rep(i,1,n)ans=work(ans,dp[n][i]);
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
    //system ("pause");
    return 0;
}