JD24. 还原
描述
输入描述
输入第一行是一个n，表示这个序列的长度。输出描述
输出仅包含一个整数，即方案数对998244353取模的结果。示例1
输入:
3 2 0 1
输出:
1
说明:
第二个数要求大于等于第一个数，则第二个数大于等于 2，且根据第二个条件，必须大于等于最后一个数，则大于等于 1 ，根据第三个条件，必须小于等于左边和右边的数的最大值，则小于等于 2 ，大于等于 2 ，所以序列只可为 2 2 1C++ 解法, 执行用时: 15ms, 内存消耗: 412KB, 提交时间: 2020-08-25
# include <iostream>
using namespace std;
const long long mod = 998244353;
const int M = 201;
long long f[2][M][3], s1[M], s2[M];
int main()
{
int n;
cin >> n;
int* a = new int[n + 1];
for(int i=1; i<=n; i++){
cin >> a[i];
}
for(int i = (a[1]?a[1]:1); i <= (a[1]?a[1]: 200); i++){
for(int j = (a[2]?a[2]:1); j <= (a[2]?a[2]:200); j++){
if(i == j)
f[0][j][1]++;
else if(i < j)
f[0][j][2]++;
}
}
for(int j = 1; j <= 200; j++){
s1[j] = s1[j-1] + f[0][j][0] + f[0][j][1] + f[0][j][2];
s2[j] = s2[j-1] + f[0][j][0] + f[0][j][1];
}
for(int i = 3; i <= n; i++){
for(int j = (a[i]?a[i]:1); j <= (a[i]?a[i]: 200); j++){
f[1][j][0] = (s2[200]-s2[j]) % mod;
f[1][j][1] = (f[0][j][0] + f[0][j][1] + f[0][j][2]) % mod;
f[1][j][2] = s1[j-1] % mod;
}
//每次i循环更新s1和s2, 滑动窗口,更新f[0],[1]
for(int j = 1; j <= 200; j++){
s1[j] = s1[j-1] + f[1][j][0] + f[1][j][1] + f[1][j][2];
s2[j] = s2[j-1] + f[1][j][0] + f[1][j][1];
f[0][j][0] = f[1][j][0]; f[0][j][1] = f[1][j][1]; f[0][j][2] = f[1][j][2];
//更新初始化
f[1][j][0] = 0; f[1][j][1] = 0; f[1][j][2] = 0;
}
}
long long res=0;
for(int j = (a[n]?a[n]:1); j <= (a[n]?a[n]: 200); j++){
res = (res + f[0][j][0] + f[0][j][1]) % mod;
}
cout << res << endl;
delete[] a;
return 0;
}
C++ 解法, 执行用时: 15ms, 内存消耗: 504KB, 提交时间: 2020-07-28
# include <iostream>
using namespace std;
const long long mod = 998244353;
const int M = 201;
long long f[2][M][3], s1[M], s2[M];
int main()
{
int n;
cin >> n;
int* a = new int[n + 1];
for(int i=1; i<=n; i++){
cin >> a[i];
}
for(int i = (a[1]?a[1]:1); i <= (a[1]?a[1]: 200); i++){
for(int j = (a[2]?a[2]:1); j <= (a[2]?a[2]:200); j++){
if(i == j)
f[0][j][1]++;
else if(i < j)
f[0][j][2]++;
}
}
for(int j = 1; j <= 200; j++){
s1[j] = s1[j-1] + f[0][j][0] + f[0][j][1] + f[0][j][2];
s2[j] = s2[j-1] + f[0][j][0] + f[0][j][1];
}
for(int i = 3; i <= n; i++){
for(int j = (a[i]?a[i]:1); j <= (a[i]?a[i]: 200); j++){
f[1][j][0] = (s2[200]-s2[j]) % mod;
f[1][j][1] = (f[0][j][0] + f[0][j][1] + f[0][j][2]) % mod;
f[1][j][2] = s1[j-1] % mod;
}
//每次i循环更新s1和s2, 滑动窗口,更新f[0],[1]
for(int j = 1; j <= 200; j++){
s1[j] = s1[j-1] + f[1][j][0] + f[1][j][1] + f[1][j][2];
s2[j] = s2[j-1] + f[1][j][0] + f[1][j][1];
f[0][j][0] = f[1][j][0]; f[0][j][1] = f[1][j][1]; f[0][j][2] = f[1][j][2];
//更新初始化
f[1][j][0] = 0; f[1][j][1] = 0; f[1][j][2] = 0;
}
}
long long res=0;
for(int j = (a[n]?a[n]:1); j <= (a[n]?a[n]: 200); j++){
res = (res + f[0][j][0] + f[0][j][1]) % mod;
}
cout << res << endl;
delete[] a;
return 0;
}