傳送門

題面：

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


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

題目大意：

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

解題：

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