Description

給出一個(gè)長度為 m 的序列 A, 請(qǐng)你求出有多少種 1…n 的排列, 滿足 A 是它的一個(gè) LIS.

Input

第一行兩個(gè)整數(shù) n,m.
接下來一行 m 個(gè)整數(shù), 表示 A.

Output

一行一個(gè)整數(shù)表示答案.

Sample Input

5 3
1 3 4

Sample Output

11

Data Constraint

對(duì)于前 30% 的數(shù)據(jù), n ≤ 9;
對(duì)于前 60% 的數(shù)據(jù), n ≤ 12;
對(duì)于 100% 的數(shù)據(jù), 1 ≤ m ≤ n ≤ 15.

Solution

• 考慮計(jì)算 LIS 時(shí)使用的經(jīng)典方法。

• 記一個(gè)數(shù)組 f ，f[i] 表示當(dāng)前長度為 i 的單調(diào)上升序列的結(jié)尾的最小值。

• 這個(gè)數(shù)組是一個(gè)單調(diào)不降的數(shù)組. 于是我們可以用二進(jìn)制來表示它。

• 設(shè) f(S,S0) 表示當(dāng)前選了集合 S 里的數(shù)，LIS 的 f 數(shù)組狀態(tài)為 S0 時(shí)的方案數(shù)。

• 這不難轉(zhuǎn)移，枚舉在末尾加上哪個(gè)數(shù)即可。

• 觀察發(fā)現(xiàn) S0 一定屬于 S，所以可以壓成三進(jìn)制。

• 每位用 0,1,2 分別表示還沒選、選了且在單調(diào)上升序列、選了但不在單調(diào)上升序列。

• 于是枚舉狀態(tài)，算出目前的單調(diào)上升序列，在枚舉還沒選的轉(zhuǎn)移即可。

• 注意枚舉轉(zhuǎn)移的數(shù)要按照 A 序列的順序來。

• 若枚舉到某一狀態(tài)，其中每個(gè)數(shù)都已經(jīng)選了，且單調(diào)上升序列的長度就是 m ，即可統(tǒng)計(jì)答案。

• 時(shí)間復(fù)雜度 O(3N?N) ，實(shí)際小很多，因?yàn)楹芏酄顟B(tài)都遍歷不到。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> using namespace std; int n,m,ans; int a[17],b[17],c[17],p[17],f[14348907+5]; bool bz[17]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } int main() {n=read(),m=read();for(int i=1;i<=m;i++){b[i]=read();if(b[i]<=b[i-1] || b[i]<1 || b[i]>n) return 0&printf("0");}for(int i=p[0]=1;i<=n;i++) p[i]=p[i-1]*3;f[0]=1;for(int i=0;i<p[n];i++)if(f[i]){bool pd=true;int tot=0,x=i;for(int j=n-1;j>=0;j--){c[j+1]=x/p[j];if(x>=p[j]){if(c[j+1]==1) a[++tot]=j+1;x%=p[j];}else pd=false;}reverse(a+1,a+1+tot);if(pd && tot==m) ans+=f[i];memset(bz,false,sizeof(bz));int num=1;while(num<=m && c[b[num]]) num++;while(num+1<=m) bz[b[++num]]=true;for(int j=1;j<=n;j++)if(!c[j] && !bz[j]){if(j>a[tot]){if(tot==m) continue;f[i+p[j-1]]+=f[i];}else{int y=upper_bound(a+1,a+1+tot,j)-a;f[i+p[j-1]+p[a[y]-1]]+=f[i];}}}printf("%d",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5600. 【NOI2018模拟3.26】Arg的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。