首页 > 代码库 > hdu3811（状态压缩dp）
hdu3811（状态压缩dp）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3811
题目大意：给定1~N个数，求出至少满足一个条件的排列总数。M个条件如下：Ai位置的数为Bi
分析：通过求出一个条件不满足的排列总数，从而间接的求出满足至少一个条件的排列总数。
dp[n][state]表示state状态下前n位不是完美排列的个数。状态转移方程为：
dp[i+1][j|(1<<k)]+=dp[i][j];这里用滚动数组来优化下空间，否则MLE。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 50010using namespace std;LL dp[2][1<<18],f[20];int vis[20][20];void init(){ f[1]=1; for(int i=2;i<=18;i++)f[i]=i*f[i-1];}int main(){ int t,n,m,x,y,cas=1; init(); scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); x--;y--; vis[x][y]=1;//标记一下，x位置不能选择y } memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++)if(!vis[0][i])dp[0][1<<i]=1;//如果第1位不是完美排列，则以该数字开头的排列值为1 int cur=0,nxt=1; for(int i=0;i<n-1;i++) { for(int j=(1<<n)-1;j>=0;j--) { if(dp[cur][j]) for(int k=0;k<n;k++) { if(j&(1<<k))continue;//数字k只能出现一次 if(vis[i+1][k])continue;//这里是第i+1位不能为k dp[nxt][j|(1<<k)]+=dp[cur][j]; //j状态变成p状态产生的排列数，p状态是j状态第i+1个位置选择了k之后的状态 } } swap(nxt,cur); } //f[n]表示n！，即n个数的全排列，减掉不满足条件的排列数，即为所求。 //dp[n-1][(1<<n)-1]表示不满足条件的排列总数，其中(1<<n)-1 对应的二进制每一个的前N个位均为1 //即该状态下n个数字都已经选择 printf("Case %d: %I64d\n",cas++,f[n]-dp[cur][(1<<n)-1]); }}
hdu3811（状态压缩dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。