HDU 2067 小兔的棋盤(pán)動(dòng)態(tài)規(guī)劃

傳送門(mén)

題面：

小兔的棋盤(pán) Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8863????Accepted Submission(s): 4613


Problem Description 小兔的叔叔從外面旅游回來(lái)給她帶來(lái)了一個(gè)禮物，小兔高興地跑回自己的房間，拆開(kāi)一看是一個(gè)棋盤(pán)，小兔有所失望。不過(guò)沒(méi)過(guò)幾天發(fā)現(xiàn)了棋盤(pán)的好玩之處。從起點(diǎn)(0，0)走到終點(diǎn)(n,n)的最短路徑數(shù)是C(2n,n),現(xiàn)在小兔又想如果不穿越對(duì)角線(xiàn)(但可接觸對(duì)角線(xiàn)上的格點(diǎn))，這樣的路徑數(shù)有多少?小兔想了很長(zhǎng)時(shí)間都沒(méi)想出來(lái)，現(xiàn)在想請(qǐng)你幫助小兔解決這個(gè)問(wèn)題，對(duì)于你來(lái)說(shuō)應(yīng)該不難吧! ?
Input 每次輸入一個(gè)數(shù)n(1<=n<=35)，當(dāng)n等于－1時(shí)結(jié)束輸入。 ?
Output 對(duì)于每個(gè)輸入數(shù)據(jù)輸出路徑數(shù)，具體格式看Sample。 ?
Sample Input

1 3 12 -1 ?
Sample Output

1 1 2 2 3 10 3 12 416024 ?
Author Rabbit ?
Source RPG專(zhuān)場(chǎng)練習(xí)賽

題目大意：

??? 給定一個(gè)方棋盤(pán)的大小，求從左下角走向右上角，每次可以選擇向上或者向右，并且路徑不能橫穿對(duì)角線(xiàn)的方案數(shù)。

解題：

??? 有點(diǎn)像入門(mén)的數(shù)塔，直接計(jì)數(shù)即可。以對(duì)角線(xiàn)為界，只計(jì)算左邊三角形的方案數(shù)，最后乘以2即可，在對(duì)角線(xiàn)上的點(diǎn)特殊處理，會(huì)爆int。

代碼：

???

#include#include#include#define?LL?long?long
using?namespace?std;
LL?dp[40][40];
int?main()
{
????memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int?i=0;i<=35;i++)
	{
		for(int?j=0;jj)
	???????{
			???dp[i+1][j]+=dp[i][j];
			???dp[i][j+1]+=dp[i][j];
		???}
???????????else?if(i==j)
		???{
????????????????dp[i+1][j]+=dp[i][j];
		???}
		???else
			???continue;
		}
	}
	int?n,cnt=1;
	while(scanf("%d",&n))
	{
		if(n==-1)break;
????????printf("%d?%d?%lldn",cnt++,n,2*dp[n][n]);
	}
	return?0;
}