解题报告『战略游戏（树形动规）』

骑猪看日落 2021-12-14 06:23 211阅读 0赞

[原题地址][Link 1]

qyx和lrl两位大佬表示可以用贪心秒了此题，但我觉得用树形动规也挺简单的。

代码实现如下：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i, a, b) for (register int i = (a); i <= (b); i++)
    
    const int maxn = 2e3;
    
    int n, num_edge = 0;
    int head[maxn], dp[maxn][5];
    
    struct node {
        int to, nxt;
    }edge[maxn << 1];
    
    int MIN(int a, int b) {
         return a < b ? a : b;}
    
    void origin() {memset(head, -1, sizeof(head));}
    
    int read() {
        int x = 0, flag = 0;
        char ch = ' ';
        while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
        if (ch == '-') {
            flag = 1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            x = (x << 1) + (x << 3) + ch - '0';
            ch = getchar();
        }
        return flag ? -x : x;
    }
    
    void addedge(int from, int to) {
        edge[++num_edge].nxt = head[from];
        edge[num_edge].to = to;
        head[from] = num_edge;
    }
    
    void DP(int u, int fa) {
        dp[u][0] = 0;
        dp[u][1] = 1;
        for (register int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (v == fa) continue;
            DP(v, u);
            dp[u][0] += dp[v][1];
            dp[u][1] += MIN(dp[v][0], dp[v][1]);
        }
    }
    
    void write(int x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
    
    int main() {
        origin();
        n = read();
        rep(i, 1, n) {
            int u, v, tot;
            u = read(), tot = read();
            rep(j, 1, tot) {
                v = read();
                addedge(u, v);
                addedge(v, u);
            }
        }
        DP(0, -1);
        write(MIN(dp[0][0], dp[0][1]));
        return 0;
    }

转载于:https://www.cnblogs.com/Kirisame-Marisa/p/10842997.html

[Link 1]: https://www.luogu.org/problemnew/show/P2016
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211213/1b2f8814d333467090058ac685bedf96.png