AtCoder Beginner Contest 199（Sponsored by Panasonic） E - Permutation (状压dp)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了 AtCoder Beginner Contest 199（Sponsored by Panasonic） E - Permutation (状压dp)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1197字，纯文字阅读大概需要2分钟。

内容图文

• 题意:一长度为\(n\)的序列,有\(m\)个限制条件,问有多少排列方法使得题目所给的\(m\)个限制条件都满足.

• 题解:\(n\)给的范围很小,我们可以状态压缩,\(v[num][j]\)表示题目所给的限制条件前\(num\)个数最多不大于\(y\)的个数,我们可以枚举所有情况,然后判断每个状态是否和题目所给的条件冲突,如果冲突,我们就不转移.

• 代码:

  #include <bits/stdc++.h>
  #define ll long long
  #define fi first
  #define se second
  #define pb push_back
  #define me memset
  #define rep(a,b,c) for(int a=b;a<=c;++a)
  #define per(a,b,c) for(int a=b;a>=c;--a)
  const int N = 1e3 + 10;
  const int mod = 1e9 + 7;
  const int INF = 0x3f3f3f3f;
  using namespace std;
  typedef pair<int,int> PII;
  typedef pair<ll,ll> PLL;
  ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
  ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
   
  int n,m;
  int v[25][25];
  ll dp[1<<20];
   
  int main() {
      ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  	cin>>n>>m;
  	rep(i,0,20){
  		rep(j,0,20){
  			v[i][j]=INF;
  		}
  	}
   
  	rep(i,1,m){
  		int x,y,z;
  		cin>>x>>y>>z;
  		v[x][y-1]=min(v[x][y-1],z);
  	}
   
  	dp[0]=1;
  	rep(i,1,(1<<n)-1){
  		int num=0;
  		rep(j,0,n-1) if(i&(1<<j)) num++;
  		int sum=0;
  		bool flag=true;
  		rep(j,0,n-1){
  			if(i&(1<<j)) sum++;
  			if(sum>v[num][j]){
  				flag=false;
  				break;
  			}
  		}
  		if(flag){
  			rep(j,0,n-1){
  				if(i&(1<<j)){
  					dp[i]+=dp[i^(1<<j)];
  				}
  			}
  		}
  	}
   
  	cout<<dp[(1<<n)-1]<<'\n';
   
      return 0;
  }
  

内容总结

以上是互联网集市为您收集整理的 AtCoder Beginner Contest 199（Sponsored by Panasonic） E - Permutation (状压dp)全部内容，希望文章能够帮你解决 AtCoder Beginner Contest 199（Sponsored by Panasonic） E - Permutation (状压dp)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---