小兔的棋盘

  这道题有两种方法，一是dp，二是用卡特兰数(事实上我觉得dp是很自然的想法)

  先说dp。对于棋盘的第0行(从下往上、从左往右数),除了(0,0)外，所有的点都只能由左边走来；对于棋盘的第0列，除了(0,0)外，所有的点都只能由左边走来。而对于对角线上的点，因为不能跨越对角线，所以这些点都只能由下边走来。而以上三种情况都不符合的点，则可以由左边或下边的点走来。故有一下dp代码：

for(int i=1;i<=35;i++)
    {
        for(int j=1;j<=35;j++)
        {
            if(i==j)
                d[i][j]+=d[i-1][j];
            else
                d[i][j]+=d[i-1][j]+d[i][j-1];
        }
    }

完整版的代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define INF 0x7fffffff
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
ll d[40][40];
void dp()
{    
    freopen("rabbit.txt","w",stdout);
    d[0][0]=1;
    mst(d,0);
    for(int col=0;col<=35;col++)
        d[0][col]=1;
    for(int row=0;row<=35;row++)
        d[row][0]=1;
    for(int i=1;i<=35;i++)
    {
        for(int j=1;j<=35;j++)
        {
            if(i==j)
                d[i][j]+=d[i-1][j];
            else
                d[i][j]+=d[i-1][j]+d[i][j-1];
        }
    }
}
int main()
{
    dp();
    ll n;
    int kase=0;
    for(int i=1;i<=35;i++)
        printf("%d %lld %lld\n",++kase,i,d[i][i]*2);
}

  第二种方法，卡特兰数。事实上我完全不知道为什么这题可以用卡特兰数来解，网上的题解说的是“细心观察，我们可以发现这道题恰好符合卡特兰数”(......)。那我们就用一下吧......

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define INF 0x7fffffff
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+5;
ll cata[40];
void get_catalan()
{
    cata[0]=1;
    for(int i=1;i<=35;i++)
        for(int j=0;j<=i-1;j++)
            cata[i]+=cata[j]*cata[i-j-1];            //抄公式。。。 
}
int main()
{
    int n;
    int kase=0;
    mst(cata,0);get_catalan();
    while(cin>>n&&n!=-1)
    {    
        kase++;
        cout<<kase<<" "<<n<<" "<<2*cata[n]<<endl;         
    }
    return 0;
}

  关于卡特兰数，可以看这个：