题解 P4815 【[CCO 2014]狼人游戏】
SuperJvRuo
2018-10-30 20:22:56
成功拿下此题首杀!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;
}
```