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

傳送門

題面：

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


Problem Description 小兔的叔叔從外面旅游回來給她帶來了一個(gè)禮物，小兔高興地跑回自己的房間，拆開一看是一個(gè)棋盤，小兔有所失望。不過沒過幾天發(fā)現(xiàn)了棋盤的好玩之處。從起點(diǎn)(0，0)走到終點(diǎn)(n,n)的最短路徑數(shù)是C(2n,n),現(xiàn)在小兔又想如果不穿越對(duì)角線(但可接觸對(duì)角線上的格點(diǎn))，這樣的路徑數(shù)有多少?小兔想了很長時(shí)間都沒想出來，現(xiàn)在想請(qǐng)你幫助小兔解決這個(gè)問題，對(duì)于你來說應(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專場練習(xí)賽

題目大意：

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

解題：

??? 有點(diǎn)像入門的數(shù)塔，直接計(jì)數(shù)即可。以對(duì)角線為界，只計(jì)算左邊三角形的方案數(shù)，最后乘以2即可，在對(duì)角線上的點(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;
}