「Codeforces 1204E」Natasha, Sasha and the Prefix Sums

题目链接:Codeforces 1204E

Description

给定$1$和$-1$的个数分别为$n$和$m$,让你统计所有$[1,-1]$序列的最大前缀和。

最大前缀和的定义是
$$f(a)=max(0,max_{1\leq i\leq l}\sum_{j=1}^{i}a_j)$$
答案对998244853取模。

Data Range

$0\leq n,m\leq 2000$

Solution


考虑$DP$,很直观可以定义$f[i][j]$表示当前选择了$i$个$1$和$j$个$-1$的答案。

然后考虑在我们当前的序列前面加上一个$1$或者$-1$。

加上$1$,那么对当前的已经构造的序列$f[i-1][j]$中所有序列都产生了$1$的贡献,而这些序列的个数为$C_{i+j-1}^{j}$。
$$f[i][j]=f[i-1][j]+C_{i+j-1}^j$$
然后对于加入的$-1$,不存在负数贡献,所以我们先计算全部的贡献再减去之前已经为$0$的个数。

所以我们再定义状态为$k[i][j]$表示我们选了$i$个$1$和$j$和$-1$的,序列最大前缀和满足$=0$的个数。

显然可以得到
$$k[i][0]=0,k[0][i]=i$$
分别表示全为$1$的不可能存在$0$的贡献,以及在全为$-1$的情况下,每一种排列都存在$1$的贡献,而且排列只有一种。

那么$k[i][j]=k[i-1][j]+k[i][j-1]$

反向用刷表法$DP$的思路考虑,假设我们知道了$f[i-1][j]$,然后我们在序列的结尾插入一个$-1$,是不是就转移到了$k[i-1][j+1]$上,这个$-1$对答案没有贡献,所以可以转移,同理$k[i][j-1]$后加一个$1$可以转移到$k[i+1][j-1]$上,这和上方的方程是等价的。

然后原来的方程就变成了:$f[i][j]=f[i][j-1]-C_{i+j-1}^{i}+k[i][j-1]$

Code

#include <bits/stdc++.h>
#define REP(i, s, t) for (int i = (s), i##ed = (t); i <= i##ed; ++ i)
#define DWN(i, s, t) for (int i = (s), i##ed = (t); i >= i##ed; -- i)
using namespace std;
const int MOD = 998244853;
const int N = 2003;
template <typename T> 
void pls(T &x, T y) { (x += y) >= MOD ? x -= MOD : 233; }
template <typename T> 
T add(T x, T y) { return x + y >= MOD ? x + y - MOD : x + y; }
template <typename T>
T sub(T x, T y) { return (x - y < 0) ? x - y + MOD : x - y; }
template <typename T>
void dec(T &x, T y) { (x -= y) < 0 ? x += MOD : 233; }
int n, m;
int f[N][N], k[N][N], C[N << 1][N << 1];
void init() {
    memset(C, 0, sizeof C);
    memset(f, 0, sizeof f); 
    C[0][0] = 1; 
    REP(i, 1, 4000) {
        C[i][0] = C[i][i] = 1; 
        REP(j, 1, i - 1) C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]); 
    }
}
int main() {
    init(); 
    cin >> n >> m;
    REP(i, 0, n) REP(j, 0, m) {
        if (i == 0) k[i][j] = 1; 
        else if (i > j) k[i][j] = 0; 
        else k[i][j] = add(k[i - 1][j], k[i][j - 1]);
    } 
    REP(i, 0, n) REP(j, 0, m) {
        if (i == 0) f[i][j] = 0; 
        else if (j == 0) f[i][j] = i; 
        else {
            pls(f[i][j], f[i - 1][j]); 
            pls(f[i][j], C[i + j - 1][j]); 
            pls(f[i][j], f[i][j - 1]); 
            dec(f[i][j], C[i + j - 1][i]);
            pls(f[i][j], k[i][j - 1]);  
        } 
    }
    cout << f[n][m] << endl; 
    return 0; 
}
最后修改:2019 年 08 月 22 日 07 : 44 PM
如果觉得我的文章对你有用,请随意赞赏

1 条评论

  1. ljc20020730

    还有一个$O(n)$的美妙做法

发表评论