题面

　　CF1024E

解析

 　　题意就是要求所有由$n$个$1$、$m$个$-1$构成的序列的最大前缀和的和

　　 算法一$(DP)$

　　 $n$， $m$都小于等于$2000$， 显然可以$DP$

　　设$dp[i][j]$表示由$i$个$1$， $j$个$-1$构成的序列的最大前缀和的和

　　$i$个$1$， $j$个$-1$构成的序列， 可以看做是在$i-1$个$1$， $j$个$-1$的序列的最前面加一个$1$得到，也可以看做是在$i$个$1$， $j-1$个$-1$的序列最前面加一个$-1$得到

　　这也就意味着，$dp[i][j]$可以由$dp[i-1][j]$与$dp[i][j-1]$转移过来

　　先考虑$dp[i-1][j]$对$dp[i][j]$的贡献，对于任意一种$i-1$个$1$， $j$个$-1$的序列， 在其首端加入一个$1$后，最大前缀和都会加$1$， 序列的个数为$C(i+j-1, j)$，因此$dp[i][j] += dp[i-1][j] + 1 * C(i-j+1, j)$

　　在考虑$dp[i][j-1]$对$dp[i][j]$的贡献，这个和上面那个不一样，要麻烦一点。因为对于最大前缀和为$0$的序列，在其首端加入一个-1后，其最大前缀和仍然是$0$， 所以$dp[i][j] += dp[i][j-1] - 1 * (C(i-j+1, j-1) - f[i][j-1])$， 其中数组$f[i][j]$表示由$i$个$1$， $j$个$-1$构成的所有序列中， 最大前缀和等于$0$的序列个数

　　因此问题变成了如何求f数组

　　与求$dp$数组的思维过程类似。 $i$个$1$， $j$个$-1$构成的序列， 可以看做是在$i-1$个$1$， $j$个$-1$的序列的最后面(注意这里是后面，而$dp$数组是在前面)加一个$1$得到，也可以看做是在$i$个$1$， $j-1$个$-1$的序列最后面加一个$-1$得到

　　对于$f$数组，显然有$i \leqslant j$，那么无论在序列末尾插入$1$或$-1$,  原来最大前缀和为$0$的序列在插入$1$或$-1$后，其最大前缀和依然为$0$，因此$f[i][j] = f[i-1][j] + f[i][j-1]$

　　状态转移方程大概就是这样了

　　初始化：

　　$f[0][i] = 1 (1 \leqslant i \leqslant m)$， 其余为$0$

　　$dp[i][0] = i (1 \leqslant i \leqslant n)$， 其余为$0$

　　答案就是$dp[n][m]$

　　时间复杂度$O(NM)$

　代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2004, mod = 998244853;

int n, m;
ll dp[maxn][maxn], f[maxn][maxn], C[maxn<<1][maxn<<1];

void init()
{
    C[0][0] = 1LL;
    for(int i = 1; i <= n + m; ++i)
    {
        C[i][0] = 1LL;
        for(int j = 1; j <= i; ++j)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    init();
    for(int i = 1; i <= m; ++i)
    {
        f[0][i] = 1;
        for(int j = 1; j <= i; ++j)
            f[j][i] = (f[j-1][i] + f[j][i-1]) % mod;
    }
    for(int i = 1; i <= n; ++i)
        dp[i][0] = i;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            dp[i][j] = (((dp[i-1][j] + C[i+j-1][j] + dp[i][j-1] - C[i+j-1][i] + f[i][j-1]) % mod) + mod) % mod;
    printf("%lld\n", dp[n][m]);
    return 0;
}

View Code