http://172.20.6.3/Problem_Show.asp?id=1388
求拓扑排序方案数 状压dp,最开始以为是拓扑排序加数论或者搜索,没想到是状压dp,突然气死.jpg;
完全没有想到状态转移的方法,syq大佬太神了orz;
写的时候太沉迷与topsort对人顺序的分组类似于斯特林数求方案数(后来发现不是),忘了最原始的满足条件(事件a在事件b前完成)即可增加方案数的简单dp……(惭愧)
所以正解就是按dp进行顺序向状态里加人,对人实现排序,显然如果必须在a前的人都加到队列里了(我这里用的是a后,嗯因为写的时候是直接看syq大佬的代码,其实我觉得记录a前的更符合逻辑)那么a就可以放到这个队列后面了。
据此,f[i]表示状态i(i上为1的位表示这一位的人放到队列里了)有多少种方案,a[x]表示x需要哪些人在前面(我写的用的是后面,毕竟从后往前和从前往后并没有什么区别…)。
第一次交爆了long long,果然long long是1A率的拦路虎,努力克服
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=;
int n,m;
int a[maxn]={};
long long f[(<<)+]={};
int main(){
scanf("%d%d",&n,&m);int x,y;
for(int i=;i<=m;i++){
scanf("%d%d",&x,&y);
a[x]|=(<<(y-));
}
int ma=<<n;f[]=;
for(int i=;i<ma;i++){
for(int j=;j<n;j++){
if((<<j)&i){
y=i-(<<j);
if((a[j+]&(~y))==){
f[i]+=f[y];
}
}
}
}
printf("%I64d\n",f[ma-]);
return ;
}