怎么做網(wǎng)站兼容性測(cè)試發(fā)布軟文廣告
終于有時(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 n n 的數(shù)組 a a a,每個(gè)數(shù)的取值范圍 a i = [ ? m , m ] a_i = [-m, m] ai?=[?m,m],問(wèn)所有滿足長(zhǎng)度 > 1 >1 >1 的子段的和為非負(fù)數(shù)的數(shù)組可能的數(shù)量。 1 ≤ n , m ≤ 5000 1\leq n,m\leq 5000 1≤n,m≤5000。
思路
看了懵哥的題解,看到狀態(tài)定義后就會(huì)了,我怎么就想不到呢?
法一
dp狀態(tài)定義 f [ i ] [ j ] : f[i][j]: f[i][j]: 前 i i i 個(gè)數(shù),最小后綴和為 j j j 的方案數(shù) j = [ ? 5000 , 5000 ] j = [-5000, 5000] j=[?5000,5000]。因?yàn)槭亲钚『缶Y和,那么如果有后綴 < ? 5000 <-5000 <?5000 的說(shuō)明至少是兩個(gè)數(shù)以上的和為負(fù)數(shù),與題意不符是不合法的方案,所以數(shù)組大小開(kāi)到 [ 0 , 10000 ] [0,10000] [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 ) O(n^3) O(n3),我們觀察一下代碼如何優(yōu)化,發(fā)現(xiàn)會(huì)有大量連續(xù)的 k k k, f [ i ] [ min ? ( j + k , k ) ] f[i][\min(j + k, k)] f[i][min(j+k,k)] 加的是同一個(gè)狀態(tài) f [ i ? 1 ] [ j ] f[i - 1][j] f[i?1][j]。那么經(jīng)典優(yōu)化方案不就來(lái)了嗎,差分前綴和優(yōu)化。
以下分情況討論:
因?yàn)槭? min ? ( j + k , k ) \min(j + k, k) min(j+k,k)
- j j j 是非正數(shù)
無(wú)論當(dāng)前 k k k 選什么, j + k ≤ k j + k \leq k j+k≤k,所以狀態(tài)一定是轉(zhuǎn)移到 j + k j + k j+k,所以對(duì)于一個(gè)非正數(shù)的 j j j 可轉(zhuǎn)移的范圍就是 0 ~ j + m 0 \sim j + m 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;// 差分 -
}
- j j j 是正數(shù)
同理無(wú)論當(dāng)前 k k k 選什么, k ≤ j + k k \leq j + k k≤j+k,所以狀態(tài)一定是轉(zhuǎn)移到 k k k,所以對(duì)于一個(gè)正數(shù) j j j,可以轉(zhuǎn)移的范圍就是 ? j ~ m -j\sim m ?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;
}