本文共 1062 字，大约阅读时间需要 3 分钟。

题意

求$[1,n]$的满足一下条件的排列方案数

对于$m$个限制,满足

$a_1,a_2...a_{x_i}$中至多有$z_i$个数小于等于$y_i$

$n<=18,m<=100$

比较裸的状压$\mathrm{D}\mathrm{P}$吧

定义$f[i]$表示填数状态为$i$时的合法方案数,第$j$位二进制为$1$表示数字$j$已经被填过

比如$i$中有$x$个$1$,说明已经填充了$k$个数

那么每次$O(n)$枚举第$k+1$个位置填哪个数,并检查是否满足$x_i=k+1$的那些限制

这样每次转移,都考虑了可能的限制

总体复杂度为$O(2^n\ast n)$,略带常数(因为有时候需要考虑$m$个限制)

#include 
   
    using namespace std;long long f[1<<18];int n,m,pre[22];typedef pair
    
     p;vector
     
vec[22];int main(){
   	cin >> n >> m;	for(int i=1;i<=m;i++)	{
   		int x,y,z; scanf("%d%d%d",&x,&y,&z);		vec[x].push_back( p(y,z) );	}	f[0] = 1;	for(int i=0;i<(1<
      
       >(j-1))&1 );		for(int j=1;j<=n;j++)	pre[j] += pre[j-1];		for(int j=1;j<=n;j++)		{
   			if( (i>>(j-1))&1 )	continue;			//在这个位置放置j			int flag = 1;			for(auto v:vec[pre[n]+1] )				if( pre[v.first]+( j<=v.first )>v.second )	flag = 0;				if( flag )	f[i|(1<<(j-1))] += f[i];		}	}	cout << f[(1<
      
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/117534549 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！