Strategic game POJ

题目链接

依旧是树形dp啦，一样的找根节点然后自下而上更新即可

设\(dp_{i,0}\)表示第i个不设，\(dp_{i,1}\)表示第i个设一个，容易得到其状态转移

\(dp_{i,0} = \sum{dp_{j,1}}(j为i的儿子节点)\)

\(dp_{i,1} = 1 + \sum{min(dp_{j,0}, dp_{j,1})}(j为i的儿子节点)\)

#include<iostream>

#include<vector>

#include<algorithm>

#include<cstring>

#include<cstdio>

using namespace std;

const int maxn = 1507;

vector<int> son[maxn];

int in[maxn], dp[maxn][2];

void dfs(int fa) {

    dp[fa][0] = 0;

    dp[fa][1] = 1;

    for(int i = 0; i < son[fa].size(); ++i) {

        int v = son[fa][i];

        dfs(v);

        dp[fa][1] += min(dp[v][0], dp[v][1]);

        dp[fa][0] += dp[v][1];

    }

}

void run_case() {

    int n;

    while(cin >> n) {

        memset(dp, 0, sizeof(dp)), memset(in, 0, sizeof(in));

        for(int i = 0; i < n; ++i) {

            int fa, num;

            scanf("%d:(%d)", &fa, &num);

            son[fa].clear();

            for(int j = 0; j < num; ++j) {

                int v;

                scanf("%d", &v);

                in[v]++;

                son[fa].push_back(v);

            }

        }

        for(int i = 0; i < n; ++i)

            if(!in[i]) {

                dfs(i);

                cout << min(dp[i][0], dp[i][1]) << "\n";

                break;

            }

    }

}

int main() {

    //ios::sync_with_stdio(false), cout.tie(0);

    cout.flags(ios::fixed);cout.precision(10);

    run_case();

    //cout.flush();

    return 0;

}

巴特西

Strategic game POJ - 1463

最新文章

热门文章