poj1463 Strategic game

缺乏、安全感 2021-11-01 23:26 238阅读 0赞

[http://poj.org/problem?id=1463][http_poj.org_problem_id_1463]

树形dp

dp\[i\]\[0/1\]表示放与不放

直接转移

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int N=1505;
    int n;
    int head[N],ver[N<<1],nxt[N<<1],ce;
    int f[N][2];
    void dfs(int now,int lst)
    {
        f[now][0]=1,f[now][1]=0;
        for(int i=head[now];i;i=nxt[i])
        {
            int y=ver[i];
            if(y==lst) continue;
            dfs(y,now);
            f[now][0]+=min(f[y][0],f[y][1]);
            f[now][1]+=f[y][0];
        }
    }
    int u,m;
    void init()
    {
        char ch[50];
        scanf("%s",ch+1);
        u=m=0;
        int i;
        for(i=1;ch[i]!=':';++i) u=u*10+ch[i]-'0';
        for(i=i+2;ch[i]!=')';++i) m=m*10+ch[i]-'0';
    }
    void adde(int a,int b)
    {
        ver[++ce]=b,nxt[ce]=head[a],head[a]=ce;
    }
    int main()
    {
         
        while(scanf("%d",&n)!=-1)
        {
            for(int i=0;i<n;++i) head[i]=0;
            ce=0;
            for(int i=1;i<=n;++i)
            {
                init();
                for(int i=1;i<=m;++i)
                {
                    int v;
                    scanf("%d",&v);
                    adde(u,v); adde(v,u);
                }
            }
            dfs(0,-1);
            printf("%d\n",min(f[0][0],f[0][1]));
        }
        
        return 0;
    }

转载于:https://www.cnblogs.com/w19567/p/11291559.html

[http_poj.org_problem_id_1463]: http://poj.org/problem?id=1463

发表评论取消回复

表情：

评论列表（有 0 条评论，238人围观）

还没有评论，来说两句吧...

相关阅读

相关【POJ2286】The Rotation Game

Solution 由于搜索量较大，我们采用IDA\算法求解。按照迭代加深搜索的基本方法，我们限制搜索深度，然后寻找在当前限制下是否存在解。为了提高算法效率，我们设

布满荆棘的人生/ 2023年06月05日 08:51/ 0 赞/ 17 阅读

相关 ACM学习-POJ-1143-Number Game

菜鸟学习ACM，纪录自己成长过程中的点滴。学习的路上，与君共勉。 ACM学习-POJ-1143-Number Game Number Game <table> <

た入场券/ 2022年09月11日 01:27/ 0 赞/ 175 阅读

相关 poj 1753 Flip Game【dfs】

Flip Game <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td

青旅半醒/ 2022年08月05日 08:22/ 0 赞/ 167 阅读

相关 poj 3710——Christmas Game

题意：给定多个无向有环图，两个人在树上博弈，问博弈结果。思路：如果没有环，则是一个标准的树上博弈，那么满足 1. 叶子节点的sg为0 2. 中间节点的sg为

喜欢ヅ旅行/ 2022年07月15日 08:56/ 0 赞/ 153 阅读

相关 poj----Game Prediction

Description Suppose there are M people, including you, playing a special card game. At

悠悠/ 2022年06月16日 01:18/ 0 赞/ 197 阅读

相关 Flip Game POJ - 1753

Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each o

以你之姓@/ 2022年06月15日 09:57/ 0 赞/ 188 阅读

相关 POJ 1753 Flip Game

Flip Game <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

迷南。/ 2021年12月23日 10:19/ 0 赞/ 210 阅读

相关 HDU1054Strategic Game(最小顶点覆盖数)

我们来先了解一下什么是最小顶点覆盖；图G的顶点覆盖是一个顶点集合V，使得G中的每一条边都接触V中的至少一个顶点。我们称集合V覆盖了G的边。最小顶点覆盖是用最少的顶点来

小鱼儿/ 2021年12月14日 00:33/ 0 赞/ 231 阅读

相关 POJ 1753 Flip Game

poj1753 题目 Flip game is played on a rectangular 4x4 field with two-sided pieces placed

蔚落/ 2021年11月11日 23:46/ 0 赞/ 225 阅读

相关 poj1463 Strategic game

[http://poj.org/problem?id=1463][http_poj.org_problem_id_1463] 树形dp dp\[i\]\[0/1\]表

缺乏、安全感/ 2021年11月01日 23:26/ 0 赞/ 239 阅读