題目大意

有n個數，讓你對其排列，令排列后的第i個數字為$s_i$，該排列要滿足：

$?i\in [1,n),s_i\le s_{i+1}$

$?i\in [1,n),\left|\begin{array}{c}(min(s_i,s_{i+1}),max(s_i,s_{i+1}))\cap \{s_j|k>i\}\end{array}\right|\le b_i$

輸出方案數

---

解題思路

設$f_{s,i}$為狀態為s，最后一個數為i的方案數

那么每次選擇一個可行的點轉移，最后取所有點都排列好的狀態即可

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 20 #define M 263000 #define wyc 4921057 using namespace std; int n,num,now,ans,a[N],b[N],v[N],f[M][N]; int main() {scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);v[a[i]]++;}for(int i=1;i<=n;++i)scanf("%d",&b[i]);for(int i=2;i<=10;++i)v[i]+=v[i-1];for(int i=1;i<=n;++i)if(!v[a[i]-1])f[1<<i-1][i]=1;for(int s=1;s<(1<<n)-1;++s){num=0;for(int i=1;i<=n;++i)if(s&(1<<i-1))num++;for(int i=1;i<=n;++i)if(s&(1<<i-1)&&f[s][i]){now=0;for(int j=i+1;j<=n&&now<=b[i];++j)if(!(s&(1<<j-1))){if(a[j]==a[i]||a[j]>a[i]&&num==v[a[i]])(f[s|(1<<j-1)][j]+=f[s][i])%=wyc;now++;}now=0;for(int j=i-1;j>0&&now<=b[i];--j)if(!(s&(1<<j-1))){if(a[j]==a[i]||a[j]>a[i]&&num==v[a[i]])(f[s|(1<<j-1)][j]+=f[s][i])%=wyc;now++;}}}for(int i=1;i<=n;++i)(ans+=f[(1<<n)-1][i])%=wyc;;printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的【状压DP】作业的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。