[ABC237F] |LIS| = 3

[ABC237F] |LIS| = 3 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这道题的技巧性很强：
考虑到最长上升子序列的长度只有3.

我们令DP[长度][所有LIS=1最后一个元素的最小值][所有LIS=2最后一个元素的最小值][所有LIS=3最后一个元素的最小值]为方案数。

为什么这样令dp呢，因为这样令可以让 LIS=1转移到LIS=2，LIS=2转移到LIS=3

重点：若dp[len][i][j][k]存在，则显然有一条重要信息：i<j<k.

技巧：显然会存在LIS=1存在，但LIS=2不存在或LIS=1和LIS=2存在，但LIS=3不存在的情况

一般来说我们默认0即不存在的条件，但是这与 i<j<k不是很符合。所以我们令 m+1为LIS=1不存在的情况，m+2为LIS=2不存在的情况,m+3为LIS=3不存在的情况，这样能满足 (i<j<k) 。

最终初始化:dp[len][m+1][m+2][m+3]=1;

对于dp[len][][][],显然枚举dp[len]的第二，第三，第四维是不好的，因为这样枚举很难转移。

但是dp[len-1][i][j][k]是知道的，我们将dp[len-1][i][j][k]转移到dp[len][][][]。

这样便只差最后一个条件,第 len 位的值，所以我们再枚举第 len 的值 p.

因为有i<j<k,所以p有四种情况。

1.p<=i<j<k.则LIS=1的最后一个元素的最小值为p：dp[len][p][j][k]=(dp[len][p][j][k]+dp[len-1][i][j][k])%MOD;

2.i<p<=j<k,则LIS=2可以 由LIS=1的 i 加一个 p组成 LIS=2，此时所有LIS=2最后一个元素的最小值为p：dp[len][i][p][k]=(dp[len][i][p][k]+dp[len-1][i][j][k])%MOD;

3.i<j<p<=k则LIS=3可以 由LIS=2的 j 加一个 p 组成LIS=3，此时所有LIS=3最后一个元素的最小值为p：dp[len][i][j][p]=(dp[len][i][j][p]+dp[len-1][i][j][k])%MOD;

4.i<j<k<p,此时LIS=4，不符合题意。

最后统计所有的dp[n][i][j][k]即可。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   
#define popb pop_back  
#define fi first
#define se second
const int N=1e3+10;
const int M=20;
const int MOD=998244353;
//const int inf=0x3f3f3f3f;     
//const ll INF=0x3ffffffffffff;
int T,n,m,dp[N][M][M][M];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    n=read(),m=read(); 
    dp[0][m+1][m+2][m+3]=1;
    for(int len=1;len<=n;len++)
        for(int i=1;i<=m+1;i++)
            for(int j=i+1;j<=m+2;j++)
                for(int k=j+1;k<=m+3;k++)
                    for(int p=1;p<=m;p++)
                    {
                        if(p<=i) dp[len][p][j][k]=(dp[len][p][j][k]+dp[len-1][i][j][k])%MOD;
                        else if(p<=j) dp[len][i][p][k]=(dp[len][i][p][k]+dp[len-1][i][j][k])%MOD;
                        else if(p<=k)  dp[len][i][j][p]=(dp[len][i][j][p]+dp[len-1][i][j][k])%MOD;
                        // p>l 就是LIS=4的情况了 
                    }
    int ans=0;
    for(int i=1;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;
    printf("%d",ans);
    return 0;
}