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; }

Day -N

快新生赛了啊啊啊啊，半个多月没碰算法题了，一直在搞ToKen的前端任务，还在搞服务器的事，感觉要凉凉。