首页 > 代码库 > 【NOIP2017模拟8.5】队伍统计
【NOIP2017模拟8.5】队伍统计
n<=20，显然要状压DP，将排队的状态压成一个数来表示
对于一个队伍状态S，令F[S][k]表示S状态违反了k条矛盾的合法方案数，则有
F[S|2i-1][k+num(S&power[i])]=F[S|2i-1][k+num(S&power[i])]+F[S][k]
其中i表示某个不在队伍的人，num(i)表示i在二进制下1的个数，power[i]表示必须排在i后面的人的情况。
（实际操作中发现power[i]储存排在i后面的人的情况的时候运行速度远不及power[i]储存排在i前面的情况）
1 #include<cstdio> 2 using namespace std; 3 const int qaq=1000000007; 4 int f[1<<20][21],power[21],n,m,t; 5 int main(){ 6 freopen("count.in","r",stdin); 7 freopen("count.out","w",stdout); 8 scanf("%d%d%d",&n,&m,&t); 9 int u,v;10 for (int i=1;i<=m;i++){11 scanf("%d%d",&u,&v);12 power[u]|=1<<(v-1); //power[v]|=1<<(u-1);13 }14 f[0][0]=1;15 for (int i=0;i<(1<<n);i++)16 for (int j=0;j<=t;j++)17 if (f[i][j])18 for (int k=1;k<=n;k++)19 if ((i&(1<<(k-1)))==0){20 int qwq=power[k]&i; //int qwq=power[k]^(power[k]&i);21 int sum=0;22 while (qwq){23 sum++;24 qwq&=(qwq-1);25 }26 if (j+sum<=t){27 f[i|(1<<(k-1))][j+sum]+=f[i][j];28 if (f[i|(1<<(k-1))][j+sum]>=qaq) 29 f[i|(1<<(k-1))][j+sum]%=qaq;30 }31 }32 int ans=0;33 for (int i=0;i<=t;i++)34 ans=(ans+f[(1<<n)-1][i])%qaq;35 printf("%d\n",ans);36 return 0;37 }
注意运算优先级，注意运算优先级，注意运算优先级！！！
【NOIP2017模拟8.5】队伍统计
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。