atcoder LIS=3

可恶啊，写了一半的题解，因为没保存，直接因为宕机嗝屁了。吐了，不写了。直接把疑惑和解答整理下吧。

题目

F - |LIS| = 3

F

题意：

给出满足以下条件的序列的数量。

1）长度为 $N(N\le 103)$，每个数的大小为 $[1,M](3\le M\le 10)$

2）最长上升子序列的长度恰好等于3

考虑到最长上升子序列的$O(nlogn)$的做法，$a[i]$表示长度为$i$的最长上升子序列中结尾最小值为$a[i]$

我们定义$ f[i][a][b][c]$ ：前i 项的序列中 长度为$1，2，3$的最长严格上升子序列中结尾的最小值为$ a,b,c$ 的数量。

比如:

序列为$[1,3,6,5]$最长上升子序列为int a[3]=[1,3,5]

如果来了一个数字0，那么a变成$[0,3,5]$，那么原来$[1,3,6,5]$这个数组的可以累加到$[1,3,6,5,0]$上，也就是$f[i-1,1,3,5]$可以累加到$f(i,0,3,5)$上

如果来了一个数字2，那么变成了$[1,2,5]$，同理可以累加到$[1,2,5]$上

如果来了4，变成$[1,3,4]$

如果来了6，那么就变成了$[1,3,5,6]$

所以可以根据最后一个数字和(a, b, c)的大小关系来确定转移的结果，当前数字x可以分成3类

KaTeX parse error: Undefined control sequence: \or at position 11: (x \le a) \̲o̲r̲ ̲(a \le x \le b)…

初始化：$f(0,m+1,m+1,m+1)=1$ 表示$a=(inf,inf,inf)$

另外最后求解$f(i,a,b,c)$ $a\le b\le c$

• 为什么计算的时候是小于等于，而不是直接小于。

​ 因为最长上升子序列严格上升的时候，找的是小于等于的。比如[1,3,3,3],严格递增的a=[1,3,INF]，等于的时候不会增加长度，如果不严格递增的最长上升子序列为[1,3,3,3]，会增加长度。而定义的dp是严格递增的最长上升子序列。所以等于的时候不会增加长度，也就可以由等于的转移过来。

• 为什么需要从x开始不是从x + 1开始。

因为[i,x, m, m]这种是满足定义的，也就是最长长度为i, 最长上升子数组为[x, m, m]，只不过最后统计的时候，不统计这种情况而已。

• 为什么是else if 而不是if: 因为每一个j只能找到一个位置要么是第一个要么是第二或者第三个。

• 为什么初始化$f[0][m][m][m]=1$。为什么不初始化其他的，为什么初始为1。

或者初始化：

$f[1][i][m][m]=1$长度为1,个人觉得这个更好理解，长度为1的最小值为i的只有一个。比如$[0],[1],[2]$.对应的a分别为$[0,m,m],[1,m,m],[2,m,m]$

扩展问题:如果不是严格递增的，能否直接把小于等于改成小于，并且统计的时候a <= b <= c？然后外面的状态不用改变，只改变转移就行了。

[m,m,m]

[1,m,m]

[1,2,m]

[1,2,2]

[1,2,2,2]

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

/**
 * @author: Zekun Fu
 * @date: 2022/10/24 10:39
 * @Description: 最长上升子序列长度为3的个数
 *
 * 1, 2, 2, 3, 3, 3, 3
 * [1, 2, 3, 4]
 * [2,2,2]
 * 给定n和m,求最长上升子序列长度为3的数组个数。
 *
 * f[i][x][y][z]:
 * 长度为i的时候，arr = [x, y, z]的情况下的最长上升子序列长度为3的个数
 * 知道当前的这个数字是j。
 * 1. 为什么计算的时候是小于等于，而不是直接小于
 * 2. 为什么需要从x开始不是从x + 1开始
 * 3. 为什么是else if 而不是if, 因为每一个j只能找到一个位置
 * 要么是第一个要么是第二或者第三个。
 * 4. 为什么初始化f[0][m][m][m] = 1。为什么不初始化其他的，为什么初始为1
 *
 * 最长上升子序列中的Lower_bound找的就是小于等于的第一个。
 * 也就是尽量向后小的那一个进行替换。从本题角度，如果当前
 * 和上一个的数组相同，那么就需要加上上一个的数组的个数。
 *
 *
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final int mod = 998244353;
        int n = sc.nextInt(), m = sc.nextInt();
        long[][][][] dp = new long [n + 1][m + 2][m + 2][m + 2];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= m; k++)
                    Arrays.fill(dp[i][j][k], 0);
            }
        }
        //dp[0][m][m][m] = 1;
        for (int i = 0; i < m; i++) dp[1][m][m][m] = 1;
        for (int i = 1; i <= n; i++) {
            for (int x = 0; x <= m; x++) {
                for (int y = x; y <= m; y++) {
                    for (int z = y; z <= m; z++) {
                        long tmp = dp[i - 1][x][y][z];
                        for (int j = 0; j < m; j++) {
                            if (j <= x) {
                                dp[i][j][y][z] = (dp[i][j][y][z] + tmp) % mod;
                            }
                            else if (j <= y) {
                                dp[i][x][j][z] = (dp[i][x][j][z] + tmp) % mod;
                            }
                            else if (j <= z) {
                                dp[i][x][y][j] = (dp[i][x][y][j] + tmp) % mod;
                            }
                        }
                    }
                }
            }
        }
        long ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                for (int k = j + 1; k < m; k++) {
                    ans = (ans + dp[n][i][j][k]) % mod;
                }
            }
        }
        System.out.println(ans);
    }
}