Codeforces Round 581

發表於 2019-08-23 更新於 2024-10-23 分類於 Codeforces ， Div2 Disqus：文章字數： 507 所需閱讀時間 ≈ 2 分鐘

E (DP + 组合数学)

又是一个大家都会的组合数学，就我不会

本题目2400评分

大意

列出n个1 m个-1的所有排列

求(每个排列的最大前缀和(>=0))的和

0<=n,m<=2000

注翻译自官方题解

k[x][y] 表示由 x个1 和y个-1组成的最大前缀和为0的数组个数

k[0][y] = 1 显然只有一种情况

k[x][y] = 0 (if x>y)

k[x][y] = k[x-1][y] + k[x][y-1]

关于上面的转移

从是最后增加一个数字转移进行考虑，分别讨论最后一位是1或-1,

1的情况，由x<=y得最大前缀和不会超过0

-1的情况，明显了增加负1不会影响前缀和

然后

dp[x][y]为方案数则 dp[n][m]为答案

dp[0][y] = 0 显然

dp[x][0] = x 显然

否则

$d[x][y] = (\binom{x+y-1}{y}+d[x-1][y]) + (d[x][y-1] - (\binom{x+y-1}{x}-k[x][y-1]))$

解释:分类首位是1或-1讨论

首位是1 剩余部分的方案数是如下组合数，对于每个方案的最大前缀和都+1了,除了首位的部分是d[x-1][y]

$\binom{x+y-1}{y} + d[x-1][y]$

首位是-1, 剩余部分的方案数是如下组合数，但并不是对于每个方案的最大前缀和都-1了，只有那些最大前缀和>0的才会影响,所以是 -1* (组合数 - (最大前缀和为0的个数)),除了首位的部分是d[x][y-1]

$d[x][y-1] - ( \binom{x+y-1}{x}-k[x][y-1])$

没有代码！

上面算法知道了，那么还剩下