题解：P10099 [ROIR 2023 Day 2] 美丽序列

cff_0102 · 2024-09-12 21:28:00 · 题解

数据范围表明这是状压 dp。

但是发现如果真的压缩状态需要使用第 i 位用 i 进制存储的方式来存储状态，太麻烦，所以干脆不压了。

设 dp_{p,a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8} 表示填到第 p 位，且上一个数 x 到第 p 位的距离为 a_x 时，填完剩下位置的方案个数。

因为当 a_x\ge x 时我们不需要关系它具体在哪个位置，只需要知道 a_x 是大于等于 x-1 的就行，所以把 a_x\ge x 的状态全部压缩成 x-1。

这里用记忆化搜索实现，每次只需要枚举第 p 位填的数即可，合法状态就继续 dfs，p=n+1 就返回 1。

#include<bits/stdc++.h>
using namespace std;
int dp[105][1][2][3][4][5][6][7][8];//dp[i][a1][a2][a3][a4][a5][a6][a7][a8]：第 p 位，且上一个 x 到第 p 位的距离为 ax 时，填的方案个数
int mod=1e9+7;
int n;
bool b[10];
int dfs(int p,int a1,int a2,int a3,int a4,int a5,int a6,int a7,int a8){
    //cout<<p<<" "<<a1<<" "<<a2<<" "<<a3<<" "<<a4<<" "<<a5<<" "<<a6<<" "<<a7<<" "<<a8<<endl;
    if(dp[p][a1][a2][a3][a4][a5][a6][a7][a8]!=-1)return dp[p][a1][a2][a3][a4][a5][a6][a7][a8];
    if(p==n+1)return 1;
    //枚举这一位填的数
    int ans=0;
    int a[10]={0,a1+1,a2+1,a3+1,a4+1,a5+1,a6+1,a7+1,a8+1};//到 i+1 的距离
    for(int i=1;i<=8;i++)if(b[i]){
        if(a[i]==i){//可以填 i
            int tmp=a[i];
            a[i]=0;//方便下一行
            ans+=dfs(p+1,min(a[1],0),min(a[2],1),min(a[3],2),min(a[4],3),min(a[5],4),min(a[6],5),min(a[7],6),min(a[8],7));
            ans%=mod;
            a[i]=tmp;//还原
        }
    }
    return dp[p][a1][a2][a3][a4][a5][a6][a7][a8]=ans;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    memset(dp,-1,sizeof(dp));
    int m;cin>>n>>m;
    while(m--){
        int x;cin>>x;b[x]=1;
    }
    cout<<dfs(1,0,1,2,3,4,5,6,7);
    return 0;
}