战略游戏

这题需要把状转方程想清楚，在动手打代码。

可能大多数人像我一样第一反应是这样的：

f[x][0]=0,f[x][1]=1;
for(int i=beg[x];i;i=nex[i])
      if(to[i]!=fa){
            dfs(to[i],x);
            f[x][0]+=f[to[i]][1];
            f[x][1]+=f[to[i]][0];
      }

然后发现WA成20pts……

实际上如果这个点要放，那么它的儿子不见得就不放。

所以应该是这样：

f[x][0]=0;f[x][1]=1;
for(int i=beg[x];i;i=nex[i])
    if(to[i]!=fa){
        dfs(to[i],x);
        f[x][0]+=f[to[i]][1];
        f[x][1]+=min(f[to[i]][1],f[to[i]][0]);
    }

看代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
int beg[maxn],nex[maxn],to[maxn],e;
inline void add(int x,int y){
    e++;nex[e]=beg[x];
    beg[x]=e;to[e]=y;
}
int n,f[maxn][5];
inline void dfs(int x,int fa){
    f[x][0]=0;f[x][1]=1;
    for(int i=beg[x];i;i=nex[i])
        if(to[i]!=fa){
            dfs(to[i],x);
            f[x][0]+=f[to[i]][1];
            f[x][1]+=min(f[to[i]][1],f[to[i]][0]);
        }
}
int main(){
    cin>>n;
    int k,x,y;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&k);
        x=x+1;
        for(int j=1;j<=k;j++){
            scanf("%d",&y);
            y=y+1;
            add(x,y),add(y,x);
        }
    }
    dfs(1,0);
    printf("%d\n",min(f[1][0],f[1][1]));
    return 0;
}

深深地感到自己的弱小。

原文链接: https://www.cnblogs.com/syzf2222/p/12461599.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/372564

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

相关推荐