Zhiwei Zhang included in Algorithm

2019-12-13 2019-12-13 143 words One minute

Contents

Description

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

Solution

由于规定不能超过对角线，可用分治的思想，只考虑沿对角线分隔开的三角形的情况，对于一个三角形中，求从$(0，0)$走到终点$(n,n)$的最短路径，观察发现无论怎么走，设到达某一点时向上走了$i$步，向右走了$j$步，都有$i \leq j$这也能通过线性规划相关知识证明。不难发现只是一个类括号匹配问题，可用$Catalan$数求解，计算$C(n)$后即是在一个三角形中的解，答案是$2C(n)$

$C(n) = \sum_{i=0}^{n-1} C(i) \cdot C(n-i-1)$ 通项公式$C(n)=\frac{C_{2n}^{n}}{n+1}$

预处理$C(n)$即可

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
typedef long long LL;
using namespace std;
LL C[100];
int main() {
	C[0] = 1;
	C[1] = 1;
	for (int i = 2; i <= 80; i++) {
		LL t = 0;
		for (int j = 0; j < i; j++)
			t += C[j]*C[i - j - 1];
		C[i] = t;
	}
	LL N;
	int cnt = 1;
	while (cin >> N) {
		if (N == -1) break;
		cout << cnt++ << " " << N << " " << C[N]*2 << endl;
	}
	return 0;
}