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

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;
}