首页 > ACM题库 > HDU-杭电 > hdu 2067 小兔的棋盘-递推-[解题报告]C++
2013
12-29

hdu 2067 小兔的棋盘-递推-[解题报告]C++

小兔的棋盘

问题描述 :

小兔的叔叔从外面旅游回来给她带来了一个礼物,小兔高兴地跑回自己的房间,拆开一看是一个棋盘,小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0,0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点),这样的路径数有多少?小兔想了很长时间都没想出来,现在想请你帮助小兔解决这个问题,对于你来说应该不难吧!

输入:

每次输入一个数n(1<=n<=35),当n等于-1时结束输入。

输出:

每次输入一个数n(1<=n<=35),当n等于-1时结束输入。

样例输入:

1
3
12
-1

样例输出:

1 1 2
2 3 10
3 12 416024

http://acm.hdu.edu.cn/showproblem.php?pid=2067

题意:一个棋盘,不穿越对角线,从(0,0)到(n,n)共有多少种走法。

比较简单的递推,注意一下初始化。。

#include <iostream>
using namespace std;
#define N 36
__int64 chessboard[N][N];

void init(){
	int i,j;
	memset(chessboard,0,sizeof(chessboard));
	for (i=0;i<N;i++)
		chessboard[i][0]=1;
	for (i=1;i<N;i++)
		for (j=1;j<=i;j++)
			chessboard[i][j]=chessboard[i-1][j]+chessboard[i][j-1];
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("2067in.txt","r",stdin);
#endif
	int n,ce=0;
	init();
	while (scanf("%d",&n)!=EOF){
		if(n==-1)
			break;
		ce++;
		printf("%d %d %I64d\n",ce,n,2*chessboard[n][n]);
	}
	return 0;
}

解题转自:http://blog.csdn.net/operator456/article/details/8548616


  1. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }