NOIP模拟题目 上升序列

来源：湘潭童程童美编程培训学校时间：2021/10/12 14:12:43

　　给出一个长度为 m 的上升序列 A(1 ≤ A[i]≤ n), 请你求出有多少种 1…n 的排列, 满足 A 是它的一个 LIS.

　　输入

　　行两个整数 n,m.

　　接下来一行 m 个整数, 表示 A.

　　输出

　　一行一个整数表示答案.

　　样例

　　【输入样例1】

　　5 3

　　1 3 4

　　【输出样例1】

　　11

　　【输入样例2】

　　4 2

　　3 4

　　【输出样例2】

　　5

　　提示

　　【数据范围与约定】

　　对于0% 的数据, n ≤ 9;

　　对于0% 的数据, n ≤ 12;

　　对于 的数据, 1 ≤ m ≤ n ≤ 15.

　　状压dp好题。

　　首先需要回忆O(nlogn) O(nlog n)" role="presentation" style="position: relative;">O(nlogn)O(nlogn) O(nlog n)O(nlogn)求lis lis" role="presentation" style="position: relative;">lislis lislis的方法，我们会维护一个单调递增的d d" role="presentation" style="position: relative;">dd dd数组。

　　可以设计状态f(s1,s2) f(s1,s2)" role="presentation" style="position: relative;">f(s1,s2)f(s1,s2) f(s1,s2)f(s1,s2)表示选取的数的集合是s1 s1" role="presentation" style="position: relative;">s1s1 s1s1，然后d数组中元素的出现情况是s2 s2" role="presentation" style="position: relative;">s2s2 s2s2。

　　这样转移是很简单的。

　　但时空都无法承受。

　　于是我们考虑优化，不难发现s1 s1" role="presentation" style="position: relative;">s1s1 s1s1是s2 s2" role="presentation" style="position: relative;">s2s2 s2s2的子集。

　　因此我们三进制状压dp就行了。

　　#include

　　#define ll long long

　　using namespace std;

　　int sta1[20],sta2[20],n,m,a[20];

　　ll f[14348908],ans=0;

　　inline void dfs(int pos,int dep,int sta){

　　if(pos==n+1){if(!dep)ans+=f[sta];return;}

　　sta+=sta2[pos-1],dfs(pos+1,dep,sta),sta+=sta2[pos-1],dfs(pos+1,dep-1,sta);

　　}

　　inline bool check(int x){

　　bool flag=1;

　　for(int i=1;i<=m;++i)

　　if((x&sta1[a[i]-1])==0)flag=0;

　　else if(!flag)return false;

　　return true;

　　}

　　int main(){

　　scanf("%d%d",&n,&m),sta1[0]=sta2[0]=1;

　　for(int i=1;i<=n;++i)sta1[i]=sta1[i-1]*2,sta2[i]=sta2[i-1]*3;

　　for(int i=1;i<=m;++i)scanf("%d",&a[i]);

　　f[0]=1;

　　for(int i=0;i

　　if(!check(i))continue;

　　int sub=i;

　　for(int sub=i;1;sub=(sub-1)&i){

　　int sta=0;

　　for(int j=1;j<=n;++j){

　　if(sub&sta1[j-1])sta+=sta2[j-1];

　　if(i&sta1[j-1])sta+=sta2[j-1];

　　}

　　if(f[sta])

　　for(int j=1;j<=n;++j){

　　if(sta/sta2[j-1]%3==0){

　　int msta=sta+2*sta2[j-1];

　　for(int k=j+1;k<=n;++k)if(msta/sta2[k-1]%3==2){msta-=sta2[k-1];break;}

　　f[msta]+=f[sta];

　　}

　　}

　　if(!sub)break;

　　}

　　}

　　dfs(1,m,0),cout<

　　return 0;

　　}

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/3482/news/421432/违者必究！ 以上就是湘潭童程童美编程培训学校 小编为您整理 NOIP模拟题目 上升序列的全部内容。