有一个含有 n 个数字的序列,每个数字的大小是不超过 200 的正整数,同时这个序列满足以下条件:
但是很不幸的是,在序列保存的过程中,有些数字丢失了,请你根据上述条件,计算可能有多少种不同的序列可以满足以上条件。
数据范围: , 序列中的数字满足 , 数字为 0 时表示丢失
输入第一行是一个n,表示这个序列的长度。
输入第二行有n个非负整数,中间用空格隔开,如果数字为0,说明这个数字丢失了,其他数字则都在1-200之间。
输出仅包含一个整数,即方案数对998244353取模的结果。
3 2 0 1
1
第二个数要求大于等于第一个数,则第二个数大于等于 2,且根据第二个条件,必须大于等于最后一个数,则大于等于 1 ,根据第三个条件,必须小于等于左边和右边的数的最大值,则小于等于 2 ,大于等于 2 ,所以序列只可为 2 2 1
#include <bits/stdc++.h> using namespace std; const int N = 1e4+3; const int M = 998244353; int main(){ int n; scanf("%d", &n); int a[n+2]; for(int i=1;i<=n;i++) scanf("%d", &a[i]); a[0] = a[n+1] = 1; long dp[n+2][203][3], s1[203], s2[203]; dp[0][1][1] = 1; for(int i=1;i<=200;i++) s1[i] = s2[i] = 1; for(int i=1;i<=n+1;i++){ int l=1, r=200; if(a[i]) l = r = a[i]; for(int j=l;j<=r;j++){ dp[i][j][0] = (s2[200]-s2[j])%M; dp[i][j][1] = (dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2])%M; dp[i][j][2] = s1[j-1]%M; } for(int j=1;j<=200;j++){ s1[j] = s1[j-1] + dp[i][j][0] + dp[i][j][1] + dp[i][j][2]; s2[j] = s2[j-1] + dp[i][j][0] + dp[i][j][1]; } } printf("%ld\n", (dp[n+1][1][0]+dp[n+1][1][1])%M); return 0; }
#include <bits/stdc++.h> using namespace std; #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define Rep(i,n) for (int i = 0; i < (n); ++i) #define For(i,s,t) for (int i = (s); i <= (t); ++i) #define rFor(i,t,s) for (int i = (t); i >= (s); --i) #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i) #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i) #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " " #define prln(x) cout << #x << " = " << x << endl #define LOWBIT(x) ((x)&(-x)) #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define ms0(a) memset(a,0,sizeof(a)) #define msI(a) memset(a,inf,sizeof(a)) #define msM(a) memset(a,-1,sizeof(a)) #define MP make_pair #define PB push_back #define ft first #define sd second template<typename T1, typename T2> istream &operator>>(istream &in, pair<T1, T2> &p) { in >> p.first >> p.second; return in; } template<typename T> istream &operator>>(istream &in, vector<T> &v) { for (auto &x: v) in >> x; return in; } template<typename T1, typename T2> ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) { out << "[" << p.first << ", " << p.second << "]" << "\n"; return out; } inline int gc(){ static const int BUF = 1e7; static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, 1, BUF, stdin); return *bg++; } inline int ri(){ int x = 0, f = 1, c = gc(); for(; c<48||c>57; f = c=='-'?-1:f, c=gc()); for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); return x*f; } typedef long long LL; typedef unsigned long long uLL; typedef pair< double, double > PDD; typedef pair< int, int > PII; typedef pair< string, int > PSI; typedef set< int > SI; typedef vector< int > VI; typedef vector< PII > VPII; typedef map< int, int > MII; typedef pair< LL, LL > PLL; typedef vector< LL > VL; typedef vector< VL > VVL; const double EPS = 1e-10; const LL inf = 0x7fffffff; const LL infLL = 0x7fffffffffffffffLL; const LL mod = 998244353; const int maxN = 1e4 + 7; const LL ONE = 1; const LL evenBits = 0xaaaaaaaaaaaaaaaa; const LL oddBits = 0x5555555555555555; int n, a[maxN]; // dp[i][j][0/1/2] 代表以a[i]为结尾,a[i] = j时的序列种数。 // 第三维代表a[i-1]和a[i]的大小关系(>, ==, <)。 LL dp[maxN][207][3]; LL preSum1[207], preSum2[207]; int main(){ INIT(); cin >> n; For(i, 1, n) cin >> a[i]; a[0] = a[n + 1] = 1;// a[-1] = 1 // 一共3个哨兵 // 预处理 dp[0][1][1] = 1; For(i, 1, 200) preSum1[i] = preSum2[i] = 1; For(i, 1, n + 1) { int s = 1, t = 200; if(a[i]) s = t = a[i]; For(j, s, t) { dp[i][j][0] = (preSum2[200] - preSum2[j]) % mod; dp[i][j][1] = (dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2]) % mod; dp[i][j][2] = preSum1[j - 1] % mod; } // 更新前缀和 For(j, 1, 200) { preSum1[j] = preSum1[j - 1] + dp[i][j][0] + dp[i][j][1] + dp[i][j][2]; preSum2[j] = preSum2[j - 1] + dp[i][j][0] + dp[i][j][1]; } } cout << (dp[n + 1][1][0]+dp[n + 1][1][1]) % mod << endl; return 0; }
//回溯法 想想都应该是超时的 错误提示时间复杂度过大 #include<iostream> (720)#include<vector> #include<algorithm> using namespace std; const long long ModNum = 998244353; long long ans = 0; void BackTrack(vector<int> &v, vector<int> temp, int i) { int maxNum; if (i == v.size()) { ans++; ans %= 998244353; return; } if (v[i] != 0) { if (i == 0) { temp.push_back(v[i]); BackTrack(v, temp, i + 1); temp.pop_back(); } else if (i == 1) { if (v[i] >= temp.back()) { temp.push_back(v[i]); BackTrack(v, temp, i + 1); temp.pop_back(); } } else { maxNum = max(temp[temp.size() - 2], v[i]); if (temp[temp.size() - 1] <= maxNum && i != v.size() - 1) { temp.push_back(v[i]); BackTrack(v, temp, i + 1); temp.pop_back(); } else if (temp[temp.size() - 1] <= maxNum && i == v.size() - 1 && v[i] <= temp.back()){ temp.push_back(v[i]); BackTrack(v, temp, i + 1); temp.pop_back(); } } } else { for (int j = 1; j <= 200; j++) { if (i == 0) { temp.push_back(j); BackTrack(v, temp, i + 1); temp.pop_back(); } else if (i == 1) { if (j >= temp.back()) { temp.push_back(j); BackTrack(v, temp, i + 1); temp.pop_back(); } } else { maxNum = max(temp[temp.size() - 2], j); if (temp[temp.size() - 1] <= maxNum && i != v.size()-1) { temp.push_back(j); BackTrack(v, temp, i + 1); temp.pop_back(); } else if (temp[temp.size() - 1] <= maxNum && i == v.size() - 1 && j <= temp.back()) { temp.push_back(j); BackTrack(v, temp, i + 1); temp.pop_back(); } } } } return; } int main(void) { int n; cin >> n; vector<int> v; int num; for (int i = 0; i < n; i++) { cin >> num; v.push_back(num); } vector<int> temp; BackTrack(v, temp, 0); cout << ans << endl; return 0; }
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); long mod = 998244353; int N = sc.nextInt(); int[] arr = new int[N + 10]; for (int i = 1; i <= N; i++) { arr[i] = sc.nextInt(); } long[][][] res = new long[N + 10][210][3]; long[] s1 = new long[210]; long[] s2 = new long[210]; //初始化 for (int i = (arr[1] == 0 ? 1 : arr[1]); i <= (arr[1] == 0 ? 200 : arr[1]); i++) { for (int j = (arr[2] == 0 ? 1 : arr[2]); j <= (arr[2] == 0 ? 200 : arr[2]); j++) { if (i == j) res[2][j][1]++; else if (i < j) res[2][j][2]++; } } for (int j = 1; j <= 200; j++) { s1[j] = s1[j - 1] + res[2][j][0] + res[2][j][1] + res[2][j][2]; s2[j] = s2[j - 1] + res[2][j][0] + res[2][j][1]; } //更新结构 for (int i = 3; i <= N; i++) { for (int j = (arr[i] == 0 ? 1 : arr[i]); j <= (arr[i] == 0 ? 200 : arr[i]); j++) { res[i][j][0] = (s2[200] - s2[j]) % mod; res[i][j][1] = (res[i - 1][j][0] + res[i - 1][j][1] + res[i - 1][j][2]) % mod; res[i][j][2] = s1[j - 1] % mod; } for (int j = 1; j <= 200; j++) { s1[j] = s1[j - 1] + res[i][j][0] + res[i][j][1] + res[i][j][2]; s2[j] = s2[j - 1] + res[i][j][0] + res[i][j][1]; } } long ans = 0; for (int j = (arr[N] == 0 ? 1 : arr[N]); j <= (arr[N] == 0 ? 200 : arr[N]); j++) { ans = (ans + res[N][j][0] + res[N][j][1]) % mod; } System.out.println(ans); } }https://www.acwing.com/solution/acwing/content/1873/