题解 | 动态规划加后缀和优化

牛客多校 $jj$ 题

以 $d{p}_{ij}dp\_\{ij\}$ 表示前 $ii$ 个数中最小后缀和为 $jj$ 的方案数

最小后缀和不会大于 $mm$ ,因为如果左边是连续的两个正数那么只会加一个，其最大值为 m

由于下标不能为负数所以将 $[-m,m][-m,m]$ 映射到 $[0,2m][0,2m]$

• 如果 $jj$ 大于等于 $00$ 由于每一个位置的数最大不超过 $mm$,如果第 $i-1i-1$ 个数小于 $j-mj-m$, 前 $ii$ 个数的最小后缀和会小于 $jj$ 于是 $d{p}_{i,j}=dp\_\{i,j\}\; =$ ${\sum }_{k=j-m}^{m}d{p}_{i-1,k}\backslash sum\_\{k\; =\; j-m\}^m\; dp\_\{i-1,k\}$

• 如果 $jj$ 小于 $00$ 由于连续至少两项的和必须大于或等于 $00$ 所以前 $i-1i-1$ 个数的最小后缀和

  必须大于 $-j-j$ 即 $d{p}_{ij}dp\_\{ij\}$ $={\sum }_{k=-j}^{m}d{p}_{i-1,k}=\; \backslash sum\_\{k\; =\; -j\}^m\; dp\_\{i-1,k\}$

  完全朴素的做法 没有经过任何优化通过率 $72.22\mathrm{\%}72.22\backslash \%$

  void solve(){
      int n,m; cin >> n >> m;
      for(int i =-m; i <= m; i++){
          dp[1][i+m] = 1;
      }
      for(int i =2; i <= n; i++){
          for(int j =-m; j <= m; j++){
              if(j < 0){
                  for(int num = -j; num <= m; num++){
                      dp[i][j+m] += dp[i-1][num+m];
                      dp[i][j+m] %= Mod;
                  }
              }
              else{
                  for(int num = j-m; num <= m; num++){
                      dp[i][j+m] += dp[i-1][num+m];
                      dp[i][j+m] %= Mod;
                  }
              }
          }
      }
      int res = 0;
      for(int i =-m; i <=m; i++){
          res += dp[n][i+m];
          res %= Mod;
      }
      cout << res << '\n';
  }
  

  ``

  考虑优化把累加利用前缀和预处理出来

  还没有用滚动数组就过了

  void solve(){
      int n,m; cin >> n >> m;
      for(int i =m; i >=  -m; --i){
          dp[1][i+m] = 1;
          suf[i+m] = suf[i+1+m]+dp[1][i+m];
      }
       //在每次循环之后都更新sum 以节省空间
      for(int i =2; i <= n; i++){
          for(int j =-m; j <= m; j++){
              if(j < 0){
                 // 从-j 到m 的和
                 dp[i][j+m] += suf[-j+m];
                 dp[i][j+m] %= Mod;
              }
              else{
                  // 实际下标为 j-m 其映射为 j
                  dp[i][j+m] += suf[j];
                  dp[i][j+m] %= Mod;
              }
          }
          // 循环结束之后 更新 suf
          suf[2*m+1] = 0;
          for(int k = m; k >= -m; k--){
              suf[k+m] = suf[k+1+m]+dp[i][k+m];
              suf[k+m]%= Mod;
          }
      }
      cout << suf[0];
  }