网站打包app,公明做网站,室内设计公司排行,固原市住房和城乡建设局网站登录—专业IT笔试面试备考平台_牛客网
题目大意#xff1a;求满足如下条件的长度为n的数组数量#xff1a;所有数字的范围在-m~m之间#xff0c;任意连续的元素数量1的区间的的区间和0
1n,m5000;
思路#xff1a;要让所有区间元素和0#xff0c; 我…登录—专业IT笔试面试备考平台_牛客网
题目大意求满足如下条件的长度为n的数组数量所有数字的范围在-m~m之间任意连续的元素数量1的区间的的区间和0
1n,m5000;
思路要让所有区间元素和0 我们只需在从左往右遍历时确保所有后缀和都0并且后缀和的最小值范围也是-m~m所以我们假如前i个数都已合法当前的后缀和最小值为j那么我们放入的下一个数字k一定满足kj0而这个k的取值又是一个连续区间所以可以用差分优化令0~2m分别对应-m,-m1...m,m-1...0然后对于jm时当前的后缀和可以转移到m~mj有dp[i1][m]dp[i][j],dp[i1][mj1]-dp[i][j]jm时可以转移到2*m-j~2*m有dp[i1][2*m-j]dp[i][j]最后对dp[n][j]求前缀和即可得到答案
//#include__msvc_all_public_headers.hpp
#includebits/stdc.h
using namespace std;
const int N 5005;
typedef long long ll;
ll dp[2][N * 2];
const ll MOD998244353;
int main()
{int n, m;cin n m;for (int i 0; i 2 * m; i){dp[1][i] 1;//第一个位置每个数都能放}int op 1;//滚动数组优化for (int i 1; i n; i){for (int j 0; j 2 * m; j){//负数和正数都是按绝对值从大到小排序的if (j m){//后缀和最小值是负数dp[op^1][m] (dp[op^1][m] dp[op][j]) % MOD;dp[op^1][j m 1] (dp[op^1][j m 1] - dp[op][j] MOD) % MOD;//转移到m~jm}else{dp[op^1][2 * m - j] (dp[op^1][2*m-j] dp[op][j])%MOD;//转移到2
*m-j~2*m}}for (int j 1; j 2 * m; j){//求差分数组前缀和dp[op^1][j] (dp[op^1][j] dp[op^1][j - 1]) % MOD;}for (int j 0; j 2 * m; j){//清空滚筒dp[op][j] 0;}op ^ 1;//滚到下一个桶}ll ans 0;for (int i 0; i 2 * m; i){//最后一次求出的前缀和即为答案ans (ans dp[op][i]) % MOD;}cout ans endl;return 0;
}
