F LIS = 3

F LIS = 3

#include #include #include #includeusing namespace std; typedef long long ll;const int MAXN = 1e6 + 10;const int mod = 998244353;int f[1001][12][12][12];int c[5];int n, m;void solve() { cin >> n >> m; f[0][m + 1][m + 1][m + 1] = 1; for (int i = 1; i<= n; i ++) { for (int j = 0; j<= m + 1; j ++) { for (int k = j; k<= m + 1; k ++) { for (int l = k; l <= m + 1; l ++) { if (!f[i - 1][j][k][l]) continue;//have ans for (int x = 1; x <= m ; x ++) { for (int y = 1; y <= 4; y ++) c[y] = m + 1; c[1] = j, c[2] = k, c[3] = l; int tot = 0; for (int y = 1; y <= 3; y ++) if (c[y] != m + 1) tot = y; if (x > c[tot]) { c[++tot] = x; } else { int p = 0; for (int y = 1; y<= tot; y ++) if (x > c[y]) p = y; c[p + 1] = x; } if (tot <= 3) (f[i][c[1]][c[2]][c[3]] += f[i - 1][j][k][l] ) %= mod; //合法的时候tot=4表示不能为3 } } } } } int ans = 0; for (int j = 0;j <= m ; j ++) { for (int k = j + 1; k <= m ; k ++) { for (int l = k +1; l <= m ; l ++) ans = (ans + f[n][j][k][l]) % mod; } } cout << ans << endl;}int main () { int t; t = 1; while (t --) solve(); return 0;}

f[i][j][k][l]表示前i个数字，最长上升子序列长度为1的最右端的最小值为j，以此推，然后加入一个新的数，需要维护这个性质，考虑最长上升子序列的优化做法。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。