【状压DP/LIS】ABC237 F - |LIS| = 3

阳光穿透心脏的1/2处 2024-03-23 14:25 60阅读 0赞

[F - |LIS| = 3 (atcoder.jp)][F - _LIS_ _ 3 _atcoder.jp]

**感觉好帅**

**尤其是jiaols的代码，怎么看都好帅**

题意：

![82951b95948242c6b5419241831bdf16.png][]

思路：

**看到10，应该想到的是暴力/状压**

做法一：

考虑简单DP

状态设计：

设dp\[i\]\[a1\]\[a2\]\[a3\]为前i个数，选的LIS为a1,a2,a3的方案数

然后按照LIS的贪心原则，如果第i+1的位置加入一个数，就把a1,a2,a3中其中一个代替掉，这里只需要分类讨论就行了，因为只有三个数，所以不需要二分

具体看代码：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e3+10;
    const int mxe=1e5+10;
    const int mod=998244353;
    
    int n,m;
    int dp[mxn][30][30][30];
    void solve(){
    	cin>>n>>m;
    	dp[0][m+1][m+1][m+1]=1;
    	for(int i=0;i<n;i++){
    		for(int a1=1;a1<=m+1;a1++){
    			for(int a2=1;a2<=m+1;a2++){
    				for(int a3=1;a3<=m+1;a3++){
    					for(int x=1;x<=m;x++){
    						if(x<=a1) dp[i+1][x][a2][a3]=(dp[i+1][x][a2][a3]+dp[i][a1][a2][a3])%mod;
    						else if(x<=a2) dp[i+1][a1][x][a3]=(dp[i+1][a1][x][a3]+dp[i][a1][a2][a3])%mod;
    						else if(x<=a3) dp[i+1][a1][a2][x]=(dp[i+1][a1][a2][x]+dp[i][a1][a2][a3])%mod;
    					}
    				}
    			}
    		}
    	}
    	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;
    			}
    		}
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

做法二：

考虑状压DP：

状态设计：

设dp\[i\]\[j\]为考虑前i个数，选的LIS方案为j的方案数

然后也是类似于前面这样转移，只不过这里用状压体现

up\_date函数就是在体现替换的过程，把第一个大于等于的替换成新加的

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=1e3+10;
    const int mxe=2e5+10;
    const int Inf=0x3f3f3f3f;
    const int mod=998244353;
    
    int n,m;
    int dp[mxn][(1<<10)]; 
    int up_date(int state,int x){
    	if(!state) return (1<<x);
    	for(int j=x;j<m;j++){
    		if((state>>j)&1){
    			return (state&(~(1<<j)))|(1<<x);
    		}
    	}
    	return state|(1<<x);
    }
    void solve(){
    	cin>>n>>m;
    	dp[0][0]=1;
    	for(int i=1;i<=n;i++){
    		for(int j=0;j<(1<<m);j++){
    			for(int k=0;k<m;k++){
    				dp[i][up_date(j,k)]=(dp[i][up_date(j,k)]+dp[i-1][j])%mod;
    			}
    		}
    	}
    	int ans=0;
    	for(int u=0;u<(1<<m);u++){
    		if(__builtin_popcount(u)==3) ans=(ans+dp[n][u])%mod;
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[F - _LIS_ _ 3 _atcoder.jp]: https://atcoder.jp/contests/abc237/tasks/abc237_f
[82951b95948242c6b5419241831bdf16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/bc7bad60a9a94bf984b0007e0a423330.png