J.Qu'est-ce Que C'est?

动态规划

题目大意

给定两个正整数 $n,mn,m$ ，要求构造长度为 $nn$ 的整数序列 $aa$ ，满足：

1. $\mathrm{\forall }i\in [1,n],-m\le a_i\le m\backslash forall\; i\backslash in\; [1,n],-m\backslash le\; a\_i\backslash le\; m$
2. 任意长度大于 $11$ 的连续子段之和不小于 $00$

求满足以上条件的整数序列的个数，结果取模

解题思路

计数取模，比起DP我会首先考虑猜通项 赛时根据样例1：$n=3,m=3\Rightarrow 130n=3,m=3\backslash Rightarrow130$ 以及手算的 $n=2,m=3\Rightarrow 28n=2,m=3\backslash Rightarrow28$ ，结合题目特征，拟出了一个满足上面两个情况的很奇怪的式子//然后样例2过不了，开摆

DP的思想是先计算出第 $ii$ 个位置前已经满足题设条件，且最小后缀和为 $jj$ 的方案数量（ $jj$ 可以是负数，因为最后一个数可以单独为负数）

考虑如何进行状态转移

对每个位置从大到小遍历当前位置填数后的最小后缀和 $jj$ ，记当前遍历到 $ii$ ，填入的数为 $xx$

1. 对于非负整数 $jj$ ，填入 $xx$ 时的方案数为 $d{p}_{i-1,j-x}dp\_\{i-1,j-x\}$

   其中 $j-x\in [-m,m],x\in [-m,m],j\ge 0\Rightarrow x\in [j-m,m]j-x\backslash in[-m,m],x\backslash in[-m,m],j\backslash ge\; 0\; \backslash Rightarrow\; x\backslash in\; [j-m,m]$，此时

   $d{p}_{i,j}={\sum }_{x=j-m}^{m}d{p}_{i-1,x}dp\_\{i,j\}=\backslash sum\backslash limits\_\{x=j-m\}^m\; dp\_\{i-1,x\}$

2. 对于负整数 $jj$ ，此时 $x=jx=j$ ，其方案数为允许 $xx$ 填入的所有方案数之和，即

   $d{p}_{i,j}={\sum }_{x=-j}^{m}d{p}_{i-1,x}dp\_\{i,j\}=\backslash sum\backslash limits\_\{x=-j\}^m\; dp\_\{i-1,x\}$

由于每次计算都用到了前一个位置的以 $mm$ 为上界的区间和，因此可以对每个位置的dp数组从 $mm$ 到 $-m-m$ 维护一个前缀和，以降低时间复杂度

复杂度

时间复杂度： $O(n^2)O(n^2)$

空间复杂度： $M(C{n}^2)M(Cn^2)$ ， $CC$ 是常数，开LL可能会导致MLE

7/30：开L都MLE了//进行了空间优化，只保留 $dpsumdpsum$ 数组

参考代码

#define O 5000 //记为0
long dp[5005][10005]={0};
//表示前i-1个数的最小后缀和为j+5000时，满足条件的可行方案数
long dpsum[5005][10005]={0};
//表示dp[i][m]到dp[i][j]可行方案数的区间和
void solve()
{
    ll m,n;
    cin >> n >> m;
    for(ll j=m;j>=-m;j--) {dp[1][j+O]=1;dpsum[1][j+O]=dpsum[1][j+1+O]+dp[1][j+O];}
    //预处理前0位
    FORLL(i,2,n){
        for(ll j=m;j>=-m;j--){
            if(j>=0) dp[i][j+O]=dpsum[i-1][j-m+O];
            //下界x+m=j => x=j-m
            else dp[i][j+O]=dpsum[i-1][-j+O];
            //j<0 下界-j
            dpsum[i][j+O]=Get_Mod(dpsum[i][j+1+O]+dp[i][j+O]);
            //计数取模
        }
    }cout << dpsum[n][-m+O] << endl;
}

7/30：空间优化后

#define O 5000 //记为0
//long dp[5001][10001]={0};//表示前i-1个数最小后缀和为j+5000，满足条件的可行方案数
long dpsum[5001][10001]={0};//表示dp[i][m]到dp[i][j]可行方案数的区间和
void solve()
{
    ll m,n;
    cin >> n >> m;
    for(ll j=m;j>=-m;j--){
        //dp[1][j+O]=1;
        //dpsum[1][j+O]=dpsum[1][j+1+O]+dp[1][j+O];
        dpsum[1][j+O]=dpsum[1][j+1+O]+1;
    }
    FORLL(i,2,n){
        for(ll j=m;j>=-m;j--){
            //if(j>=0) dp[i][j+O]=dpsum[i-1][j-m+O];//下界x+m=j => x=j-m
            if(j>=0) dpsum[i][j+O]=Get_Mod(dpsum[i][j+1+O]+dpsum[i-1][j-m+O]);
            //else dp[i][j+O]=dpsum[i-1][-j+O];//j<0 下界-j
            else dpsum[i][j+O]=Get_Mod(dpsum[i][j+1+O]+dpsum[i-1][-j+O]);
            //dpsum[i][j+O]=Get_Mod(dpsum[i][j+1+O]+dp[i][j+O]);
            
        }
    }cout << dpsum[n][-m+O] << endl;
}