南阳定制网站制作价格低,怎么设置微信小程序,上海做saas平台网站的公司,网站建设技术支持祥云平台终于有时间来慢慢补补题了
J Qu’est-ce Que C’est?
作为队内的dp手#xff0c;赛时想了好久#xff0c;等学弟学妹都出了还是不会#xff0c;羞愧#xff0c;还好最终队友做出来了。 链接J Qu’est-ce Que C’est?
题意
长度为 n n n 的数组 a a a#xff0c;每…终于有时间来慢慢补补题了
J Qu’est-ce Que C’est?
作为队内的dp手赛时想了好久等学弟学妹都出了还是不会羞愧还好最终队友做出来了。 链接J Qu’est-ce Que C’est?
题意
长度为 n n n 的数组 a a a每个数的取值范围 a i [ − m , m ] a_i [-m, m] ai[−m,m]问所有满足长度 1 1 1 的子段的和为非负数的数组可能的数量。 1 ≤ n , m ≤ 5000 1\leq n,m\leq 5000 1≤n,m≤5000。
思路
看了懵哥的题解看到状态定义后就会了我怎么就想不到呢 法一 dp状态定义 f [ i ] [ j ] : f[i][j]: f[i][j]: 前 i i i 个数最小后缀和为 j j j 的方案数 j [ − 5000 , 5000 ] j [-5000, 5000] j[−5000,5000]。因为是最小后缀和那么如果有后缀 − 5000 -5000 −5000 的说明至少是两个数以上的和为负数与题意不符是不合法的方案所以数组大小开到 [ 0 , 10000 ] [0,10000] [0,10000] 即可离散化后。
我们先不管时间复杂度根据dp定义先敲个状态转移出来代码如下
#include bits/stdc.h
using namespace std;#define ll long longconst int N 5010, mod 998244353;int f[N][N * 2]; // 前i个数最小后缀和为j的方案数 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 --){ // 枚举当前a_i选哪个数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;
}
时间复杂度为 O ( n 3 ) O(n^3) O(n3)我们观察一下代码如何优化发现会有大量连续的 k k k f [ i ] [ min ( j k , k ) ] f[i][\min(j k, k)] f[i][min(jk,k)] 加的是同一个状态 f [ i − 1 ] [ j ] f[i - 1][j] f[i−1][j]。那么经典优化方案不就来了吗差分前缀和优化。
以下分情况讨论 因为是 min ( j k , k ) \min(j k, k) min(jk,k) j j j 是非正数 无论当前 k k k 选什么 j k ≤ k j k \leq k jk≤k所以状态一定是转移到 j k j k jk所以对于一个非正数的 j j j 可转移的范围就是 0 ∼ j m 0 \sim j m 0∼jm。
// 区间 [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 是正数 同理无论当前 k k k 选什么 k ≤ j k k \leq j k k≤jk所以状态一定是转移到 k k k所以对于一个正数 j j j可以转移的范围就是 − 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个数最小后缀和为j的方案数 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]);}}*/// 考虑差分前缀和优化// j 是 负数 k 是正数 f[i][j k m] 从0 ~ m j// j 是 正数 k 是负数/正数 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;
}
