終于有時(shí)間來(lái)慢慢補(bǔ)補(bǔ)題了

J Qu’est-ce Que C’est?

作為隊(duì)內(nèi)的dp手，賽時(shí)想了好久，等學(xué)弟學(xué)妹都出了還是不會(huì)，羞愧，還好最終隊(duì)友做出來(lái)了。
鏈接J Qu’est-ce Que C’est?

題意

長(zhǎng)度為 $n$ 的數(shù)組 $a$，每個(gè)數(shù)的取值范圍 $a_i=[?m,m]$，問(wèn)所有滿足長(zhǎng)度 $>1$ 的子段的和為非負(fù)數(shù)的數(shù)組可能的數(shù)量。$1\le n,m\le 5000$。

思路

看了懵哥的題解，看到狀態(tài)定義后就會(huì)了，我怎么就想不到呢？
法一
dp狀態(tài)定義 $f[i][j]:$ 前 $i$ 個(gè)數(shù)，最小后綴和為 $j$ 的方案數(shù) $j=[?5000,5000]$。因?yàn)槭亲钚『缶Y和，那么如果有后綴 $<?5000$ 的說(shuō)明至少是兩個(gè)數(shù)以上的和為負(fù)數(shù)，與題意不符是不合法的方案，所以數(shù)組大小開(kāi)到 $[0,10000]$ 即可（離散化后）。

我們先不管時(shí)間復(fù)雜度，根據(jù)dp定義先敲個(gè)狀態(tài)轉(zhuǎn)移出來(lái)，代碼如下：

#include <bits/stdc++.h>
using namespace std;#define ll long longconst int N = 5010, mod = 998244353;int f[N][N * 2]; // 前i個(gè)數(shù)，最小后綴和為j的方案數(shù) j = [-5000, 5000]void add(int& a, int b){a = (a + b) % mod;
}
int main(){int n, m;cin >> n >> m;f[0][2 * m] = 1;for(int i = 1; i <= n; i ++){for(int j = -m; j <= m; j ++){ // 枚舉最小后綴for(int k = m; k >= -m; k --){ // 枚舉當(dāng)前a_i選哪個(gè)數(shù)if(j + k < 0) break;add(f[i][min(j + k, k) + m], f[i - 1][j + m]);}}}int ans = 0;for(int i = -m; i <= m; i ++){add(ans, f[n][i + m]);}cout << ans;return 0;
}

時(shí)間復(fù)雜度為 $O(n^3)$，我們觀察一下代碼如何優(yōu)化，發(fā)現(xiàn)會(huì)有大量連續(xù)的 $k$，$f[i][\min (j+k,k)]$ 加的是同一個(gè)狀態(tài) $f[i?1][j]$。那么經(jīng)典優(yōu)化方案不就來(lái)了嗎，差分前綴和優(yōu)化。

以下分情況討論：
因?yàn)槭?$\min (j+k,k)$

1. $j$ 是非正數(shù)
   無(wú)論當(dāng)前 $k$ 選什么，$j+k\le k$，所以狀態(tài)一定是轉(zhuǎn)移到 $j+k$，所以對(duì)于一個(gè)非正數(shù)的 $j$ 可轉(zhuǎn)移的范圍就是 $0～j+m$。

// 區(qū)間 [l, r] + val  f_l + val  f_{r + 1} + val
for(int j = -m; j <= 0; j ++){f[i][m] = (f[i][m] + f[i - 1][j + m]) % mod;// 差分 +f[i][m + j + m + 1] = (f[i][m + j + m + 1] + mod - f[i - 1][j + m]) % mod;// 差分 -
}

2. $j$ 是正數(shù)
   同理無(wú)論當(dāng)前 $k$ 選什么，$k\le j+k$，所以狀態(tài)一定是轉(zhuǎn)移到 $k$，所以對(duì)于一個(gè)正數(shù) $j$，可以轉(zhuǎn)移的范圍就是 $?j～m$。

for(int j = 1; j <= m; j ++){f[i][-j + m] = (f[i][-j + m] + f[i - 1][j + m]) % mod;f[i][m + m + 1] = (f[i][m + m + 1] + mod - f[i - 1][j + m]) % mod;
}

完整代碼

#include <bits/stdc++.h>
using namespace std;#define ll long longconst int N = 5010, mod = 998244353;int f[N][N * 2]; // 前i個(gè)數(shù)，最小后綴和為j的方案數(shù) j = [-5000, 5000]void add(int& a, int b){a = (a + b) % mod;
}
int main(){int n, m;cin >> n >> m;f[0][2 * m] = 1;for(int i = 1; i <= n; i ++){/*for(int j = -m; j <= m; j ++){for(int k = m; k >= -m; k --){if(j + k < 0) break;add(f[i][min(j + k, k) + m], f[i - 1][j + m]);}}*/// 考慮差分前綴和優(yōu)化// j 是 負(fù)數(shù) k 是正數(shù) f[i][j + k + m] 從0 ~ m + j// j 是 正數(shù) k 是負(fù)數(shù)/正數(shù) f[i][k + m] 從-j ~ mfor(int j = -m; j <= 0; j ++){f[i][m] = (f[i][m] + f[i - 1][j + m]) % mod; // 差分 +f[i][m + j + m + 1] = (f[i][m + j + m + 1] + mod - f[i - 1][j + m]) % mod; // 差分 -}for(int j = 1; j <= m; j ++){f[i][-j + m] = (f[i][-j + m] + f[i - 1][j + m]) % mod;f[i][m + m + 1] = (f[i][m + m + 1] + mod - f[i - 1][j + m]) % mod;}for(int j = -m + 1; j <= m; j ++){ // 前綴和f[i][j + m] = (f[i][j + m] + f[i][j + m - 1]) % mod;}}int ans = 0;for(int i = -m; i <= m; i ++){add(ans, f[n][i + m]);}cout << ans;return 0;
}