题解 P4815 【[CCO 2014]狼人游戏】

SuperJvRuo

2018-10-30 20:22:56

Solution

成功拿下此题首杀!NOIP提高组水平的选手们,只要认真读题,就可以做出来。 - 没有机器人又被指控又被保护 - 没有机器人被指控或保护一次以上 - 如果有一个编号为$A$机器人指控或保护编号为$B$的机器人,那么我们保证$A<B$。 这三条限定为什么会使题目更简单呢? 因为它保证了这个图是树形图的集合。我们就可以把这道题当做树形DP来做。 先对每个树形图单独做DP。对于每个树形图中的每个节点,有两种转移: 对于一条“指控”边,狼人儿子可以转移到平民父亲,平民儿子可以转移到狼人或平民父亲; 对于一条“保护”边,平民儿子可以转移到平民父亲,狼人儿子可以转移到狼人或平民父亲。 最后对所有树形图做DP,统计答案,具体的转移方程见代码。 f数组如果不滚动的话,像我这样开得大一点,大概是$205\times205\times2\times205\times8\div2^{20}=131MB$,似乎还是滚动一下比较好。 ``` #include<cstdio> #include<vector> #define LL long long #define MOD 1000000007 struct Edge { int to,next,eff; //eff==1表示指控,eff==2表示保护 }edge[205]; int head[205],cnt; void Add_edge(int u,int v,int opt) { edge[++cnt]=(Edge){v,head[u],opt}; head[u]=cnt; } std::vector<int> root; LL f[205][2][2][205]; //f[i][j(滚动)][0/1][j]:以i为根的子树,算到第j个儿子,i是/不是狼人,子树中有j个狼人的方案数 int size[205],son[205]; int indeg[205],outdeg[205]; //入度为0的点一定是一个树形图的根 //求出子树大小、每个节点的儿子数量 void dfs(int u) { size[u]=1; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].to; ++son[u]; dfs(v); size[u]+=size[v]; } } void calc(int u) { f[u][0][1][1]=f[u][0][0][0]=1; for(int i=head[u],num=1;i;i=edge[i].next,num^=1) { int v=edge[i].to; calc(v); for(int j=0;j<=size[u];++j) { f[u][num][0][j]=f[u][num][1][j]=0; for(int k=0;k<=size[v];++k) { if(j>=k) { //平民父亲可以由狼人或平民转移 f[u][num][0][j]+=(f[u][num^1][0][j-k])*(f[v][son[v]&1][0][k]+f[v][son[v]&1][1][k]); if(edge[i].eff==1) {//狼人一定指控平民 f[u][num][1][j]+=(f[u][num^1][1][j-k])*(f[v][son[v]&1][0][k]); } else {//狼人一定保护狼人 f[u][num][1][j]+=(f[u][num^1][1][j-k])*(f[v][son[v]&1][1][k]); } f[u][num][0][j]%=MOD; f[u][num][1][j]%=MOD; } } } } } LL res[205][205]; //前i个树形图,含j个狼人的方案数 void solve(int n,int w) { for(int i=1;i<=n;++i) { if(!indeg[i]) { root.push_back(i); } } res[0][0]=1; //dp起点,0个狼人的方案数为1 for(int i=0;i<(int)root.size();++i) { dfs(root[i]); calc(root[i]); for(int j=0;j<=size[root[i]];++j) { for(int k=0;k<=w;++k) { if(k>=j) { res[i+1][k]+=res[i][k-j]*(f[root[i]][son[root[i]]&1][1][j]+f[root[i]][son[root[i]]&1][0][j]); res[i+1][k]%=MOD; } } } } } int main() { int n,w,m; scanf("%d%d%d",&n,&w,&m); char opt[5]; int u,v; for(int i=0;i<m;++i) { scanf("%s %d %d",opt,&u,&v); ++indeg[v]; ++outdeg[u]; Add_edge(u,v,opt[0]=='A'?1:2); } solve(n,w); printf("%lld",res[(int)root.size()][w]); return 0; } ```