CodeForces 1204E"Natasha, Sasha and the Prefix Sums"（动态规划 or 组合数学--卡特兰数的应用）
•题意
由 n个1和m个-1组成的 $C_{n+m}^{n}$ 个序列；对所有序列的最大前缀和求和；
并规定最大前缀和最小是
0；
•题解
定义 $(i,j)$ 表示序列由 i 个 1，j 个 -1 组成；
$(i,j)$ 共有 $C_{i+j}^{i}$ 种不同的组合方式；
$(i-1,j)$ 共有 $C_{i+j-1}^{i-1}$ 种不同的组合方式；
$(i,j-1)$ 共有 $C_{i+j-1}^{i}$ 种不同的组合方式；
如果同时在 $(i-1,j)$ 的 $C_{i+j-1}^{i-1}$ 和 $(i,j-1)$ 的 $C_{i+j-1}^{i}$ 种组合方式的末尾或开头分别插入 1 或 -1；
那便是 $(i,j)$ 的不同的组合方式的种类数，即 $C_{i+j}^{i}=C_{i+j-1}^{i-1}+C_{i+j-1}^{i}$；
根据 n,m 的范围（$\leq 2000$），考虑用 DP 解决这道题目；
首先，定义 $dp[i][j]$ 表示由 $(i,j)$ 组成的 $C_{i+j}^{i}$ 个序列，对所有序列的最大前缀和求和后的结果；
有上述前置知识，很容易想到 $(i,j)$ 可由 $(i-1,j)$ 和 $(i,j-1)$ 得到；
这也就是说，$dp[i][j]$ 可由 $dp[i-1][j]$ 和 $dp[i][j-1]$ 转移过来；
因为 $(i,j)$ 可由 $(i-1,j)$ 和 $(i,j-1)$ 的末尾或开头插入 1 或 -1 得到，那到底是在开头插入还是结尾插入呢？
因为题意让求的是前缀最大值之和，所以，我们考虑到在开头插入 1 或 -1；
- 在 $(i-1,j)$ 的开头插入 1，也就意味着这 $C_{i+j-1}^{i-1}$ 个序列的前缀最大值都会增加 1，那么
- $dp[i][j] += dp[i-1][j]+C_{i+j-1}^{i-1}$
- 在 $(i,j-1)$ 的开头插入 -1，意味着这 $C_{i+j-1}^{i}$ 个序列的前缀最大值会减少 1，那么
- $dp[i][j] += dp[i][j-1]-C_{i+j-1}^{i}+h[i][j-1]$